[PATCH] Avoid `SCM_VALIDATE_LIST ()'

[PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

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

Hello,

This is a followup to this discussion:

  http://thread.gmane.org/gmane.lisp.guile.devel/7194

The attached patch changes several list-related functions so that they
don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).

A side-effect (besides performance improvements) is that all these
functions will now happily traverse circular lists, and will silently
deal with dotted lists.  This is acceptable behavior IMO.

Nevertheless, the second patch below implements the "tortoise and the
hare" in `list-copy' so that it detects circular list; it seems
worthwhile to check that here since `list-copy' would otherwise exhaust
memory.

(Note that SRFI-1's `list-copy' *does* accept improper lists, including
circular lists, although SRFI-1 does not explicitly mention that it
should handle improper list.)

Also, in some cases, the `wrong-type-arg' message is different (but the
exception key is the same).

OK to apply to both branches?

Thanks,
Ludo'.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: First patch --]
[-- Type: text/x-patch, Size: 7130 bytes --]

From 8df8aaafb2bed534db5e7a3a9337cd9c8f38523c Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Sun, 31 Aug 2008 23:04:10 +0200
Subject: [PATCH] Avoid using `SCM_VALIDATE_LIST ()' since it has O(n) complexity.

* libguile/list.c (scm_reverse_x, scm_list_copy, scm_memq, scm_memv,
  scm_member, scm_filter, scm_filter_x): Don't use
  `SCM_VALIDATE_LIST ()' since it's O(n).  Use `SCM_VALIDATE_CONS ()'
  when traversing the input lists.

* srfi/srfi-1.c (scm_srfi1_concatenate, scm_srfi1_concatenate_x):
  Don't use `SCM_VALIDATE_LIST ()' on LSTLST; instead, simply make
  sure it's either the empty list or a pair.
  (scm_srfi1_member, scm_srfi1_remove, scm_srfi1_remove_x): Don't use
  `SCM_VALIDATE_LIST ()' since it's O(n).  Use `SCM_VALIDATE_CONS ()'
  when traversing the input lists.
---
 NEWS            |    7 +++++++
 libguile/list.c |   40 +++++++++++++++++++++++++++-------------
 srfi/srfi-1.c   |   22 +++++++++++++++-------
 3 files changed, 49 insertions(+), 20 deletions(-)

diff --git a/NEWS b/NEWS
index c2bed17..cfcd43b 100644
--- a/NEWS
+++ b/NEWS
@@ -56,6 +56,13 @@ When you use GDS to evaluate Scheme code from Emacs, you can now use
 This makes these internal functions technically not callable from
 application code.
 
+** Remove argument type checking with `list?' in some list-related functions
+
+Several list-related functions (e.g., `memq', `list-copy', etc.) used
+R5RS `list?' to validate their arguments.  However, `list?' has linear
+complexity, so these functions have been changed to not resort to
+`list?'.
+
 ** `guile-config link' now prints `-L$libdir' before `-lguile'
 ** Fix memory corruption involving GOOPS' `class-redefinition'
 ** Fix build issue on Tru64 and ia64-hp-hpux11.23 (`SCM_UNPACK' macro)
diff --git a/libguile/list.c b/libguile/list.c
index a1a79a4..8b0a2e4 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004
+/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004,2008
  * Free Software Foundation, Inc.
  * 
  * This library is free software; you can redistribute it and/or
@@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
   else
-    SCM_VALIDATE_LIST (2, new_tail);
+    SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail),
+		new_tail, 2, FUNC_NAME);
 
   while (!SCM_NULL_OR_NIL_P (lst))
     {
-      SCM old_tail = SCM_CDR (lst);
+      SCM old_tail;
+
+      SCM_VALIDATE_CONS (1, lst);
+
+      old_tail = SCM_CDR (lst);
       SCM_SETCDR (lst, new_tail);
       new_tail = lst;
       lst = old_tail;
@@ -546,7 +550,8 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
   SCM * fill_here;
   SCM from_here;
 
-  SCM_VALIDATE_LIST (1, lst);
+  SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst),
+	      lst, 1, FUNC_NAME);
 
   newlst = SCM_EOL;
   fill_here = &newlst;
@@ -613,8 +618,13 @@ SCM_DEFINE (scm_memq, "memq", 2, 0, 0,
 	    "returned.")
 #define FUNC_NAME s_scm_memq
 {
-  SCM_VALIDATE_LIST (2, lst);
-  return scm_c_memq (x, lst);
+  for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
+    {
+      SCM_VALIDATE_CONS (2, lst);
+      if (scm_is_eq (SCM_CAR (lst), x))
+	return lst;
+    }
+  return SCM_BOOL_F;
 }
 #undef FUNC_NAME
 
@@ -629,9 +639,9 @@ SCM_DEFINE (scm_memv, "memv", 2, 0, 0,
 	    "returned.")
 #define FUNC_NAME s_scm_memv
 {
-  SCM_VALIDATE_LIST (2, lst);
   for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
     {
+      SCM_VALIDATE_CONS (2, lst);
       if (! scm_is_false (scm_eqv_p (SCM_CAR (lst), x)))
 	return lst;
     }
@@ -650,9 +660,9 @@ SCM_DEFINE (scm_member, "member", 2, 0, 0,
 	    "empty list) is returned.")
 #define FUNC_NAME s_scm_member
 {
-  SCM_VALIDATE_LIST (2, lst);
   for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
     {
+      SCM_VALIDATE_CONS (2, lst);
       if (! scm_is_false (scm_equal_p (SCM_CAR (lst), x)))
 	return lst;
     }
@@ -884,9 +894,11 @@ SCM_DEFINE (scm_filter, "filter", 2, 0, 0,
   SCM walk;
   SCM *prev;
   SCM res = SCM_EOL;
+
   SCM_ASSERT (call, pred, 1, FUNC_NAME);
-  SCM_VALIDATE_LIST (2, list);
-  
+  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
+	      list, 2, FUNC_NAME);
+
   for (prev = &res, walk = list;
        scm_is_pair (walk);
        walk = SCM_CDR (walk))
@@ -910,9 +922,11 @@ SCM_DEFINE (scm_filter_x, "filter!", 2, 0, 0,
   scm_t_trampoline_1 call = scm_trampoline_1 (pred);
   SCM walk;
   SCM *prev;
+
   SCM_ASSERT (call, pred, 1, FUNC_NAME);
-  SCM_VALIDATE_LIST (2, list);
-  
+  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
+	      list, 2, FUNC_NAME);
+
   for (prev = &list, walk = list;
        scm_is_pair (walk);
        walk = SCM_CDR (walk))
diff --git a/srfi/srfi-1.c b/srfi/srfi-1.c
index 35815b3..e330d43 100644
--- a/srfi/srfi-1.c
+++ b/srfi/srfi-1.c
@@ -279,7 +279,8 @@ SCM_DEFINE (scm_srfi1_concatenate, "concatenate", 1, 0, 0,
 	    "limit.")
 #define FUNC_NAME s_scm_srfi1_concatenate
 {
-  SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
+  SCM_ASSERT (scm_is_pair (lstlst) || SCM_NULL_OR_NIL_P (lstlst),
+	      lstlst, 1, FUNC_NAME);
   return scm_append (lstlst);
 }
 #undef FUNC_NAME
@@ -297,7 +298,8 @@ SCM_DEFINE (scm_srfi1_concatenate_x, "concatenate!", 1, 0, 0,
 	    "limit.")
 #define FUNC_NAME s_scm_srfi1_concatenate
 {
-  SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
+  SCM_ASSERT (scm_is_pair (lstlst) || SCM_NULL_OR_NIL_P (lstlst),
+	      lstlst, 1, FUNC_NAME);
   return scm_append_x (lstlst);
 }
 #undef FUNC_NAME
@@ -1582,7 +1584,7 @@ SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0,
 #define FUNC_NAME s_scm_srfi1_member
 {
   scm_t_trampoline_2 equal_p;
-  SCM_VALIDATE_LIST (2, lst);
+
   if (SCM_UNBNDP (pred))
     equal_p = equal_trampoline;
   else
@@ -1592,6 +1594,7 @@ SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0,
     }
   for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
     {
+      SCM_VALIDATE_CONS (2, lst);
       if (scm_is_true (equal_p (pred, x, SCM_CAR (lst))))
 	return lst;
     }
@@ -1898,13 +1901,16 @@ SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0,
   SCM walk;
   SCM *prev;
   SCM res = SCM_EOL;
+
   SCM_ASSERT (call, pred, 1, FUNC_NAME);
-  SCM_VALIDATE_LIST (2, list);
-  
+  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
+	      list, 2, FUNC_NAME);
+
   for (prev = &res, walk = list;
        scm_is_pair (walk);
        walk = SCM_CDR (walk))
     {
+      SCM_VALIDATE_CONS (2, walk);
       if (scm_is_false (call (pred, SCM_CAR (walk))))
 	{
 	  *prev = scm_cons (SCM_CAR (walk), SCM_EOL);
@@ -1930,9 +1936,11 @@ SCM_DEFINE (scm_srfi1_remove_x, "remove!", 2, 0, 0,
   scm_t_trampoline_1 call = scm_trampoline_1 (pred);
   SCM walk;
   SCM *prev;
+
   SCM_ASSERT (call, pred, 1, FUNC_NAME);
-  SCM_VALIDATE_LIST (2, list);
-  
+  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
+	      list, 2, FUNC_NAME);
+
   for (prev = &list, walk = list;
        scm_is_pair (walk);
        walk = SCM_CDR (walk))
-- 
1.6.0


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: Second patch --]
[-- Type: text/x-patch, Size: 2527 bytes --]

From 7b24df6656a86a06fc7c7430d8e56a762d88da10 Mon Sep 17 00:00:00 2001
From: =?utf-8?q?Ludovic=20Court=C3=A8s?= <ludo@gnu.org>
Date: Sun, 31 Aug 2008 23:48:17 +0200
Subject: [PATCH] Report an error for circular lists in `list-copy'.

* libguile/list.c (scm_list_copy): Use the "tortoise and the hare"
  algorithm to detect circular lists and report an error.

* test-suite/tests/list.test (list-copy): New tests.
---
 libguile/list.c            |   18 ++++++++++++++++--
 test-suite/tests/list.test |   16 +++++++++++++++-
 2 files changed, 31 insertions(+), 3 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 8b0a2e4..256c1fd 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -548,14 +548,14 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
 {
   SCM newlst;
   SCM * fill_here;
-  SCM from_here;
+  SCM from_here, hare;
 
   SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst),
 	      lst, 1, FUNC_NAME);
 
   newlst = SCM_EOL;
   fill_here = &newlst;
-  from_here = lst;
+  from_here = hare = lst;
 
   while (scm_is_pair (from_here))
     {
@@ -564,6 +564,20 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
       *fill_here = c;
       fill_here = SCM_CDRLOC (c);
       from_here = SCM_CDR (from_here);
+
+      /* Use the "tortoise and the hare" algorithm to detect circular
+	 lists.  */
+      if (scm_is_pair (hare))
+	{
+	  hare = SCM_CDR (hare);
+	  if (scm_is_pair (hare))
+	    {
+	      hare = SCM_CDR (hare);
+	      if (scm_is_pair (hare))
+		SCM_ASSERT (!scm_is_eq (hare, from_here),
+			    lst, 1, FUNC_NAME);
+	    }
+	}
     }
   return newlst;
 }
diff --git a/test-suite/tests/list.test b/test-suite/tests/list.test
index 7dc0ef0..514fe2a 100644
--- a/test-suite/tests/list.test
+++ b/test-suite/tests/list.test
@@ -1,5 +1,5 @@
 ;;;; list.test --- tests guile's lists     -*- scheme -*-
-;;;; Copyright (C) 2000, 2001, 2006 Free Software Foundation, Inc.
+;;;; Copyright (C) 2000, 2001, 2006, 2008 Free Software Foundation, Inc.
 ;;;; 
 ;;;; This library is free software; you can redistribute it and/or
 ;;;; modify it under the terms of the GNU Lesser General Public
@@ -655,6 +655,20 @@
 
 ;;; list-copy
 
+(with-test-prefix "list-copy"
+
+  (pass-if "empty list"
+    (null? (list-copy '())))
+
+  (pass-if "non-empty list"
+    (let ((lst (iota 123)))
+      (equal? (list-copy lst) lst)))
+
+  (pass-if-exception "circular list"
+    exception:wrong-type-arg
+    (let ((lst (list 1)))
+      (set-cdr! lst lst)
+      (list-copy lst))))
 
 ;;; memq
 
-- 
1.6.0

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
> Hello,
> 
> This is a followup to this discussion:
> 
>   http://thread.gmane.org/gmane.lisp.guile.devel/7194
> 
> The attached patch changes several list-related functions so that they
> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
> 
> A side-effect (besides performance improvements) is that all these
> functions will now happily traverse circular lists, and will silently
> deal with dotted lists.  This is acceptable behavior IMO.
> 
> Nevertheless, the second patch below implements the "tortoise and the
> hare" in `list-copy' so that it detects circular list; it seems
> worthwhile to check that here since `list-copy' would otherwise exhaust
> memory.
> 
> (Note that SRFI-1's `list-copy' *does* accept improper lists, including
> circular lists, although SRFI-1 does not explicitly mention that it
> should handle improper list.)
> 
> Also, in some cases, the `wrong-type-arg' message is different (but the
> exception key is the same).
> 
> OK to apply to both branches?

-  return scm_c_memq (x, lst);
+  for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
+    {
+      SCM_VALIDATE_CONS (2, lst);

Looks cleaner to use SCM_CONS_P (or whatever it is called) as loop guard,
so it is obviously correct, and crash if the lst is not properly terminated 
after the loop (- perhaps only if we're not compiling in optimizing mode).

On a tangent, is anyone still seriously considering to run Emacs atop GUILE?
(It looks a bit like a travesty if we're trying to accomodate elisp while
also trying to follow standards like SRFI-x and RxRS)  

-  SCM from_here;
+  SCM from_here, hare;

you could do the init to lst right here.  IMO it's neater not to have uninitialized
memory locations during program execution.

 ;;;; list.test --- tests guile's lists     -*- scheme -*-
-;;;; Copyright (C) 2000, 2001, 2006 Free Software Foundation, Inc.
+;;;; Copyright (C) 2000, 2001, 2006, 2008 Free Software Foundation, Inc.

Can we do this in one fell swoop, adding 2008 to all files?  After all publishing 
a commit is a release in some sense.  Then, we don't have to worry about the file
headers anymore.


-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/1 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?

Running a whole Emacs on top of Guile? - no.

Running some Emacs Lisp code on top of Guile? - yes.

But I admit that what I have in mind is still vaporware right now.  So
I guess that if Guile's current infrastructure for trying to support
Elisp became a serious obstacle to progress, we should not rule out
dropping it.

> +  for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> +    {
> +      SCM_VALIDATE_CONS (2, lst);
>
> Looks cleaner to use SCM_CONS_P (or whatever it is called) as loop guard,
> so it is obviously correct, and crash if the lst is not properly terminated
> after the loop (- perhaps only if we're not compiling in optimizing mode).

I don't think we should do that.  I agree that the code would _look_
cleaner and more obviously correct, but in fact the code _is_ correct,
and changing it would lose the Elisp support.  And I don't think the
code as it stands is (anywhere near) so obscure as to justify losing
that.

Regards,
     Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hi,

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> -  return scm_c_memq (x, lst);
> +  for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> +    {
> +      SCM_VALIDATE_CONS (2, lst);
>
> Looks cleaner to use SCM_CONS_P (or whatever it is called) as loop guard,
> so it is obviously correct, and crash if the lst is not properly terminated 
> after the loop (- perhaps only if we're not compiling in optimizing mode).

Two things: `SCM_NULL_OR_NIL_P ()' is different from `scm_is_pair ()',
and `SCM_NULL_OR_NIL_P ()' can be passed any object so it does work if
LST is a dotted list.

> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?

There's Ken Reaburn's attempt at http://www.mit.edu/~raeburn/guilemacs/ ,
and there's also the Elisp support that's under `lang'.  I don't think
the former is really maintained.  The latter isn't actively maintained
either but I think it's in a pretty good shape.  Neil?

> -  SCM from_here;
> +  SCM from_here, hare;
>
> you could do the init to lst right here.  IMO it's neater not to have uninitialized
> memory locations during program execution.

I find it nicer to have initialization right before the first use.  I'd
write it like this:

  for (from_here = hare = lst;
       !SCM_NULL_OR_NIL_P (from_here);
       from_here = SCM_CDR (from_here))

but I was trying to minimize changes.

> -;;;; Copyright (C) 2000, 2001, 2006 Free Software Foundation, Inc.
> +;;;; Copyright (C) 2000, 2001, 2006, 2008 Free Software Foundation, Inc.
>
> Can we do this in one fell swoop, adding 2008 to all files?

I wouldn't do that.  I think updating the copyright year *when* a change
is made is better: it allows people to see at a glance whether a file
has been changed at all recently and avoids pointless commits.  I use
this Emacs hook, which makes it painless:

  (add-hook 'write-file-hooks 'copyright-update)

However, the GNU maintainer's guide (see (info "(maintain) Copyright
Notices")) prefers the other way:

     To update the list of year numbers, add each year in which you have
  made nontrivial changes to the package.  (Here we assume you're using a
  publicly accessible revision control server, so that every revision
  installed is also immediately and automatically published.)  When you
  add the new year, it is not required to keep track of which files have
  seen significant changes in the new year and which have not.  It is
  recommended and simpler to add the new year to all files in the
  package, and be done with it for the rest of the year.

Thanks,
Ludo'.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
>> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?
> 
> There's Ken Reaburn's attempt at http://www.mit.edu/~raeburn/guilemacs/ ,
> and there's also the Elisp support that's under `lang'.  I don't think
> the former is really maintained.  The latter isn't actively maintained
> either but I think it's in a pretty good shape.  Neil?

What is the intended use case of running Elisp in GUILE ?  Is anyone using it
for anything?


>> -;;;; Copyright (C) 2000, 2001, 2006 Free Software Foundation, Inc.
>> +;;;; Copyright (C) 2000, 2001, 2006, 2008 Free Software Foundation, Inc.
>>
>> Can we do this in one fell swoop, adding 2008 to all files?
> 
> I wouldn't do that.  I think updating the copyright year *when* a change
> is made is better: it allows people to see at a glance whether a file
> has been changed at all recently 

I think that 

  git log FILE

is the reliable and precise way to check that.  The headers are so much 
boilerplate that I pretty much ignore all of them.

> and avoids pointless commits.

We could add 2008 to all files in a single commit, and avoid poluting 
diffs with header blah blah for an entire year.

> However, the GNU maintainer's guide (see (info "(maintain) Copyright
> Notices")) prefers the other way:
> 
>      To update the list of year numbers, add each year in which you have
>   made nontrivial changes to the package.  (Here we assume you're using a
>   publicly accessible revision control server, so that every revision
>   installed is also immediately and automatically published.)  When you
>   add the new year, it is not required to keep track of which files have
>   seen significant changes in the new year and which have not.  It is
>   recommended and simpler to add the new year to all files in the
>   package, and be done with it for the rest of the year.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/2 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> What is the intended use case of running Elisp in GUILE ?  Is anyone using it
> for anything?

I would like to have the GDS elisp code, running in Guile, displaying
debugging information in Gtk (or Qt, or X) windows, without a full
Emacs present.

Why?
- I think it would be a cool hack.
- For small environments like the Nokia tablets and Openmoko, where it
might be tricky to have a full Emacs.

Will it actually ever happen and work?  I'm afraid I don't know.

>>> -;;;; Copyright (C) 2000, 2001, 2006 Free Software Foundation, Inc.
>>> +;;;; Copyright (C) 2000, 2001, 2006, 2008 Free Software Foundation, Inc.
>>>
>>> Can we do this in one fell swoop, adding 2008 to all files?
>>
>> I wouldn't do that.  I think updating the copyright year *when* a change
>> is made is better: it allows people to see at a glance whether a file
>> has been changed at all recently
>
> I think that
>
>  git log FILE
>
> is the reliable and precise way to check that.  The headers are so much
> boilerplate that I pretty much ignore all of them.
>
>> and avoids pointless commits.
>
> We could add 2008 to all files in a single commit, and avoid poluting
> diffs with header blah blah for an entire year.

FWIW, I don't have a strong view on this.  I'm happy with anything
that FSF are happy with, and that makes the job of updating the
copyrights easy.

     Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/1 Ludovic Courtès <ludo@gnu.org>:
>
> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
>> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?
>
> There's Ken Reaburn's attempt at http://www.mit.edu/~raeburn/guilemacs/ ,
> and there's also the Elisp support that's under `lang'.  I don't think
> the former is really maintained.  The latter isn't actively maintained
> either but I think it's in a pretty good shape.  Neil?

Yes, I would say so, and I still work on it from time to time.

    Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ken Raeburn]

On Sep 1, 2008, at 16:30, Ludovic Courtès wrote:
>> On a tangent, is anyone still seriously considering to run Emacs  
>> atop GUILE?
>
> There's Ken Reaburn's attempt at http://www.mit.edu/~raeburn/guilemacs/ 
>  ,
> and there's also the Elisp support that's under `lang'.  I don't think
> the former is really maintained.  The latter isn't actively maintained
> either but I think it's in a pretty good shape.  Neil?

Still keeping it in the back of my mind, but first my attempts to use  
SVK to mirror the Emacs repository broke (naturally, after it had  
looked solid enough that I had switched to it for my Emacs development  
work), and now Guile uses git, which I've never picked up, and some  
Emacs folks are talking about changing to yet another source control  
system.  (BTW, are people aware that the www.gnu.org pages for guile  
list an ftp snapshot site that has in fact not been updated since last  
September?  For people not interested in downloading, installing, and  
learning N new source control systems, daily or weekly snapshots are  
handy.)

I'm thinking that if I do pick this project up again, it'll probably  
be with released versions of Guile; as long as Emacs continues to use  
CVS, I can easily stay current with that.

I did play with it a little bit a few months ago, and found one  
annoying problem:

I'm using a Mac as my main machine these days.  The Emacs unexec  
mechanism interacts badly with the Mac version of malloc, so Emacs  
uses its own version specially tailored to use Mac system allocation  
routines in a way that works with unexec.  Guile doesn't have any  
hooks for doing that sort of thing.  Of course you can configure with - 
Dmalloc=unexec_malloc and so on, but then you're guaranteed not to be  
able to build an actual guile interpreter executable without the extra  
Emacs code.  An alternative is to set up Emacs to not use unexec, but  
that's uncommon enough a configuration that you can't always expect it  
to work -- or expect anyone else to be terribly interested in why  
Emacs-without-unexec (even without Guile-related hacks) behaves  
strangely.

My work -- as far as it had progressed -- has nothing to do with  
converting lisp to scheme or anything like that.  My "phase one"  
project keeps all the lisp evaluation code intact, and while both  
interpreters could conceivably be used and objects from each language  
might even be visible to the other, they may have totally different  
types -- like lisp strings with their text properties and such could  
be smobs in guile...

Ken

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

Hi Ken,

2008/9/7 Ken Raeburn <raeburn@raeburn.org>:
>
> Still keeping it in the back of my mind, but first my attempts to use SVK to
> mirror the Emacs repository broke (naturally, after it had looked solid
> enough that I had switched to it for my Emacs development work), and now
> Guile uses git, which I've never picked up, and some Emacs folks are talking
> about changing to yet another source control system.  (BTW, are people aware
> that the www.gnu.org pages for guile list an ftp snapshot site that has in
> fact not been updated since last September?  For people not interested in
> downloading, installing, and learning N new source control systems, daily or
> weekly snapshots are handy.)

Noted, thanks.  I'll try to fix that up.

> I did play with it a little bit a few months ago, and found one annoying
> problem:
>
> I'm using a Mac as my main machine these days.  The Emacs unexec mechanism
> interacts badly with the Mac version of malloc, so Emacs uses its own
> version specially tailored to use Mac system allocation routines in a way
> that works with unexec.  Guile doesn't have any hooks for doing that sort of
> thing.  Of course you can configure with -Dmalloc=unexec_malloc and so on,
> but then you're guaranteed not to be able to build an actual guile
> interpreter executable without the extra Emacs code.

Not sure I understand.  Surely you would always know if you're
building with or without the Emacs code, and so could define malloc or
not accordingly?

Regards,
      Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ken Raeburn]

On Sep 7, 2008, at 11:24, Neil Jerram wrote:
>> I'm using a Mac as my main machine these days.  The Emacs unexec  
>> mechanism
>> interacts badly with the Mac version of malloc, so Emacs uses its own
>> version specially tailored to use Mac system allocation routines in  
>> a way
>> that works with unexec.  Guile doesn't have any hooks for doing  
>> that sort of
>> thing.  Of course you can configure with -Dmalloc=unexec_malloc and  
>> so on,
>> but then you're guaranteed not to be able to build an actual guile
>> interpreter executable without the extra Emacs code.
>
> Not sure I understand.  Surely you would always know if you're
> building with or without the Emacs code, and so could define malloc or
> not accordingly?

Not if you want to build and install the full guile package and then  
link emacs against libguile, which is how I've generally done it.  Or  
if you want to build both emacs and guile executables at once so you  
can test libguile without the rest of emacs.  Of course, I could just  
drop a copy of guile into the source tree and tweak the build process  
to skip the 'guile' binary, or add wrapper functions that only link  
into that executable and cause the redirected calls to invoke malloc  
and friends after all.

I could also create function-pointer variables that could be changed  
before guile initialization, and I may do it that way for my own use,  
but it's not clear to me that there'd be any value in feeding that  
back upstream.

Ken

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Ken Raeburn <raeburn@raeburn.org>:
>
> Not if you want to build and install the full guile package and then link
> emacs against libguile, which is how I've generally done it.  Or if you want
> to build both emacs and guile executables at once so you can test libguile
> without the rest of emacs.  Of course, I could just drop a copy of guile
> into the source tree and tweak the build process to skip the 'guile' binary,
> or add wrapper functions that only link into that executable and cause the
> redirected calls to invoke malloc and friends after all.

OK, I see now.

> I could also create function-pointer variables that could be changed before
> guile initialization, and I may do it that way for my own use, but it's not
> clear to me that there'd be any value in feeding that back upstream.

Agreed, that's probably not worthwhile initially, until the
Emacs/Guile work advances to the point where others could try it out.

      Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Neil Jerram <neiljerram@googlemail.com>:
> 2008/9/7 Ken Raeburn <raeburn@raeburn.org>:
>>
>> Still keeping it in the back of my mind, but first my attempts to use SVK to
>> mirror the Emacs repository broke (naturally, after it had looked solid
>> enough that I had switched to it for my Emacs development work), and now
>> Guile uses git, which I've never picked up, and some Emacs folks are talking
>> about changing to yet another source control system.  (BTW, are people aware
>> that the www.gnu.org pages for guile list an ftp snapshot site that has in
>> fact not been updated since last September?  For people not interested in
>> downloading, installing, and learning N new source control systems, daily or
>> weekly snapshots are handy.)
>
> Noted, thanks.  I'll try to fix that up.

Snapshots as of now are up at
http://www.ossau.uklinux.net/guile/snapshots, and I hope they will
keep automagically appearing there.

In case anyone feels like reviewing and commenting on it, I've also
uploaded the `make-snap' script that generates these, in the same
directory.

If all seems well after a few days, I'll update the www.gnu.org pages
accordingly.

      Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hi Neil,

"Neil Jerram" <neiljerram@googlemail.com> writes:

> Snapshots as of now are up at
> http://www.ossau.uklinux.net/guile/snapshots, and I hope they will
> keep automagically appearing there.

Looks good!  I think you can already update the web page since the
current link is broken anyway.

Thanks!

Ludo'.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/9 Ludovic Courtès <ludo@gnu.org>:
> Hi Neil,
>
> "Neil Jerram" <neiljerram@googlemail.com> writes:
>
>> Snapshots as of now are up at
>> http://www.ossau.uklinux.net/guile/snapshots, and I hope they will
>> keep automagically appearing there.
>
> Looks good!  I think you can already update the web page since the
> current link is broken anyway.

I've done that now.

     Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Andy Wingo]

On Sun 31 Aug 2008 17:12, Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?
> (It looks a bit like a travesty if we're trying to accomodate elisp while
> also trying to follow standards like SRFI-x and RxRS)  

I think it makes a *lot* of sense to compile elisp to the VM. I don't
plan on doing so myself, but if the VM gets good enough, it could be
enhanced with the instructions that elisp needs, if any, and it would be
possible to run emacs lisp code, and possibly even emacs itself, on
guile.

Guile-VM already has a language-agnostic compiler, repl, etc. Scheme
compilation starts with a language-specific reader then translation to
GHIL, at which point the generic compilation proceeds. You could plug in
an elisp reader and translator (see
module/language/scheme/translate.scm) to GHIL, or compile directly to
GLIL.

I don't know where the boundary lies regarding C primitives, though. I
think we'll eventually want to make VM-implemented functions as fast or
faster than the C ones, through a tracing JIT or something. So you could
make elisp reference different C primitives, or implement its primitives
in elisp (or scheme, or whatever), or make our C primitives do both.

I don't know how this impacts the current patch though -- probably not
at all :)

Andy
-- 
http://wingolog.org/

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Andy Wingo escreveu:
> On Sun 31 Aug 2008 17:12, Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
> 
>> On a tangent, is anyone still seriously considering to run Emacs atop GUILE?
>> (It looks a bit like a travesty if we're trying to accomodate elisp while
>> also trying to follow standards like SRFI-x and RxRS)  
> 
> I think it makes a *lot* of sense to compile elisp to the VM. I don't
> plan on doing so myself, but if the VM gets good enough, it could be
> enhanced with the instructions that elisp needs, if any, and it would be
> possible to run emacs lisp code, and possibly even emacs itself, on
> guile.
> 
> Guile-VM already has a language-agnostic compiler, repl, etc. Scheme
> compilation starts with a language-specific reader then translation to
> GHIL, at which point the generic compilation proceeds. You could plug in
> an elisp reader and translator (see
> module/language/scheme/translate.scm) to GHIL, or compile directly to
> GLIL.

Well, I remember having a flamewar with RMS about language agnosticism
and running emacs on GUILE about 8 years ago, and I don't think we
have progressed much since then.  Extrapolating this pace,  I think
it's a waste of time.

> I don't know where the boundary lies regarding C primitives, though. I
> think we'll eventually want to make VM-implemented functions as fast or
> faster than the C ones, through a tracing JIT or something. So you could
> make elisp reference different C primitives, or implement its primitives
> in elisp (or scheme, or whatever), or make our C primitives do both.

Actually, on a complete tangent:

There is a large industry movement trying to optimize the hell out of
JavaScript, since it is used in browsers.  How much sense does it make
to translate Scheme or LISP to JavaScript and have (for example) V8 or
tracemonkey handle it?  I'm not very familiar with JavaScript, but I
recall it shared lots of characteristics with LISP.  I am fairly
certain that we will never out-optimize (for example) V8.



-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Andy Wingo]

I don't know why I'm answering this, but...

On Thu 04 Sep 2008 17:10, Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Well, I remember having a flamewar with RMS about language agnosticism
> and running emacs on GUILE about 8 years ago, and I don't think we
> have progressed much since then.  Extrapolating this pace,  I think
> it's a waste of time.

8 years?? Anyway. I just mentioned things that guile-vm can do. If they
don't get done that means they're not important.

> How much sense does it make to translate Scheme or LISP to JavaScript
> and have (for example) V8 or tracemonkey handle it?

I think for some people it will make sense, but such a beast would not
be Guile.

Andy.
-- 
http://wingolog.org/

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/5 Andy Wingo <wingo@pobox.com>:
> I don't know why I'm answering this, but...
>
> On Thu 04 Sep 2008 17:10, Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
>> Well, I remember having a flamewar with RMS about language agnosticism
>> and running emacs on GUILE about 8 years ago, and I don't think we
>> have progressed much since then.  Extrapolating this pace,  I think
>> it's a waste of time.
>
> 8 years?? Anyway. I just mentioned things that guile-vm can do. If they
> don't get done that means they're not important.

I was going to write the same thing - then saw that Andy had already done so.

People work on what interests them, in the time they have spare.  I
know we've lost in the global scripting language competition, but I
still find this language implementation fun.

>> How much sense does it make to translate Scheme or LISP to JavaScript
>> and have (for example) V8 or tracemonkey handle it?
>
> I think for some people it will make sense, but such a beast would not
> be Guile.

Agree there too.

     Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

On Sat, Sep 6, 2008 at 7:45 PM, Neil Jerram <neiljerram@googlemail.com> wrote:
>>> Well, I remember having a flamewar with RMS about language agnosticism
>>> and running emacs on GUILE about 8 years ago, and I don't think we
>>> have progressed much since then.  Extrapolating this pace,  I think
>>> it's a waste of time.
>>
>> 8 years?? Anyway. I just mentioned things that guile-vm can do. If they
>> don't get done that means they're not important.
>
> I was going to write the same thing - then saw that Andy had already done so.
>
> People work on what interests them, in the time they have spare.  I
> know we've lost in the global scripting language competition, but I
> still find this language implementation fun.

I am not using and enhancing GUILE primarily for fun.  A large part of
the lilypond architecture in written in it, and performance problems
in GUILE often translate directly to problems in LilyPond.  The reason
I delved in the GC years ago was because lily was spending half of its
time running GUILE's GC.

I feel using GUILE has been a big mistake -especially considering the
amount of time I sank into it.  I seriously looked into moving lily to
mzscheme, but I lack the bandwidth to do that now.

I hope you can understand that I have a somewhat different basic
attitude wrt GUILE development.

--
Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Han-Wen Nienhuys <hanwenn@gmail.com>:
>
> I am not using and enhancing GUILE primarily for fun.  A large part of
> the lilypond architecture in written in it, and performance problems
> in GUILE often translate directly to problems in LilyPond.  The reason
> I delved in the GC years ago was because lily was spending half of its
> time running GUILE's GC.
>
> I feel using GUILE has been a big mistake -especially considering the
> amount of time I sank into it.  I seriously looked into moving lily to
> mzscheme, but I lack the bandwidth to do that now.
>
> I hope you can understand that I have a somewhat different basic
> attitude wrt GUILE development.

I'm sorry to hear that.  Personally, I hugely appreciate the time that
you've invested in Guile's GC.  I wish I understood the GC fully
myself, so I could help more with that work.

        Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> 2008/9/7 Han-Wen Nienhuys <hanwenn@gmail.com>:
>> I am not using and enhancing GUILE primarily for fun.  A large part of
>> the lilypond architecture in written in it, and performance problems
>> in GUILE often translate directly to problems in LilyPond.  The reason
>> I delved in the GC years ago was because lily was spending half of its
>> time running GUILE's GC.
>>
>> I feel using GUILE has been a big mistake -especially considering the
>> amount of time I sank into it.  I seriously looked into moving lily to
>> mzscheme, but I lack the bandwidth to do that now.
>>
>> I hope you can understand that I have a somewhat different basic
>> attitude wrt GUILE development.
> 
> I'm sorry to hear that.  Personally, I hugely appreciate the time that
> you've invested in Guile's GC.  I wish I understood the GC fully
> myself, so I could help more with that work.

Actually, since the couple of cleanups (or as some on this list like
to say: 'cleanups') I did, the GC has become a lot more simple.  It's
not really that difficult, you just have to take a more global view of
the interpreter.  The nice thing about GC is that if you break it, it
tends break all over the place in obvious ways.  Usually, you can't
even get to the 'guile>' prompt.

Please feel free to dive in and bug me with questions. I am always
very eager to help people that will take over code maintenance duties
from me :-)



-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> Actually, since the couple of cleanups (or as some on this list like
> to say: 'cleanups') I did, the GC has become a lot more simple.

Actually I did get that impression, from my look so far at your
cleanup patch - i.e. that it is now easier to understand than it was
in the past.  But I need to spend more time on it.

Since you mention 'cleanups', I must say that I agree with Ludovic,
that it would have been preferable to post the patch for
review/discussion before committing it, since that is our (majority)
current practice.  Sure there may have been a few exceptions, but only
for trivial changes, I believe, and I don't believe that this was -
overall - a trivial change.  (I'm aware that it has lots of trivial
bits in it, but I don't think it's all trivial.)

(I also think it's arguable that actually committing to a branch is
more convenient, for author and reviewers, than juggling emails - but
that then leads on to other questions, like what expectations people
can have of the "master" branch, and why we are using Git like CVS...)

> It's
> not really that difficult, you just have to take a more global view of
> the interpreter.  The nice thing about GC is that if you break it, it
> tends break all over the place in obvious ways.  Usually, you can't
> even get to the 'guile>' prompt.

That is indeed a good point!

> Please feel free to dive in and bug me with questions. I am always
> very eager to help people that will take over code maintenance duties
> from me :-)

Will do, thanks.

         Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> Since you mention 'cleanups', I must say that I agree with Ludovic,
> that it would have been preferable to post the patch for
> review/discussion before committing it, since that is our (majority)
> current practice.  Sure there may have been a few exceptions, but only
> for trivial changes, I believe, and I don't believe that this was -
> overall - a trivial change.  (I'm aware that it has lots of trivial
> bits in it, but I don't think it's all trivial.)
> 
> (I also think it's arguable that actually committing to a branch is
> more convenient, for author and reviewers, than juggling emails - but
> that then leads on to other questions, like what expectations people
> can have of the "master" branch, and why we are using Git like CVS...)

If we want to code review as a policy, I'm fine with that, but let's do 
it in a structured way then.

Guido van Rossum wrote a webtool for code review, which should be fairly easy
to use and setup 

   http://code.google.com/appengine/articles/rietveld.html

and I heard people have recently added Git support to it.

How about using this for Guile?  (We need to figure out how to set it up, and
contributors need to have gmail addresses, but that should not be a problem, 
is it?)

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Andy Wingo]

Hi,

On Sun 07 Sep 2008 04:33, "Han-Wen Nienhuys" <hanwenn@gmail.com> writes:

> I am not using and enhancing GUILE primarily for fun.

Then why do it?

I'm serious.

> I feel using GUILE has been a big mistake -especially considering the
> amount of time I sank into it.  I seriously looked into moving lily to
> mzscheme, but I lack the bandwidth to do that now.

FWIW, I would like to run my code on other schemes -- not the same goal
as this one, but it overlaps considerably. For me, I think that the path
will be implementation of some scheme standard that supports modules,
then migrating code over to that standard. I'm not sure about R6 though.

> I hope you can understand that I have a somewhat different basic
> attitude wrt GUILE development.

I understand your frustrations, believe me. But excuse my being blunt,
but these frustratons seem to have made you bitter and confrontational.
All attitudes are not equal. This one is not the best for Guile.

Andy.
-- 
http://wingolog.org/

Re: development goals (was: [PATCH] Avoid `SCM_VALIDATE_LIST ()')

[Han-Wen Nienhuys]

Andy Wingo escreveu:
>> I am not using and enhancing GUILE primarily for fun.
> 
> Then why do it?
> 
> I'm serious.

Because I take my (LilyPond) users serious. 

OK - I will admit that interpreter/GC hacking is cool, but on the
downside, when I try to do anything, the intertia/resistance I feel in
the community here is a big turnoff for me.

>> I feel using GUILE has been a big mistake -especially considering the
>> amount of time I sank into it.  I seriously looked into moving lily to
>> mzscheme, but I lack the bandwidth to do that now.
> 
> FWIW, I would like to run my code on other schemes -- not the same goal
> as this one, but it overlaps considerably. For me, I think that the path
> will be implementation of some scheme standard that supports modules,
> then migrating code over to that standard. I'm not sure about R6 though.

Is there a Rx/SRFI standard for modules? I always thought that module 
system(s) was one of the unspecified areas.

>> I hope you can understand that I have a somewhat different basic
>> attitude wrt GUILE development.
> 
> I understand your frustrations, believe me. But excuse my being blunt,
> but these frustratons seem to have made you bitter and confrontational.

FWIW, I have always been a bit confrontational.

> All attitudes are not equal. This one is not the best for Guile.

I think Guile does not have any desire to be anything. Therefore "best
for Guile" does not exist; it is the people that develop it and the
people who use it who have desires.

I am probably the only person who is in both camps currently.

When working with the devs here I continue to be puzzled by what the
objectives are.  For instance, we had 5 major (stable) releases in 11
years.  I have always wanted this rate to go up, and have tried argue
for that, but with 1.10 (or 2.0, whatever it is called) being in
preparation for 2.5 years at this moment, I don't see this changing.

At such a glacial pace of development, you would imagine that backward
compatibility would not be a concern - after all, who plans for
compatibility over a five year span, yet Guile continues to support
(by default!) the GH interface which was deprecated in 2002 (or was it
with version 1.4 in 2000?).

For LilyPond (and any other package that uses Guile, eg. texmacs,
snd), this is a problem, since we can not realistically ship anything
that requires the latest Git/CVS version to work.  Hence, my
improvements in LilyPond are held back by Guile's release scheme.  For
example, I wanted to use SCM rationals for various purposes in Lily
for a long time, but had to wait for the 1.8 release before I could do
this.

If anything, my impression so far is that the objective is to produce
a piece of perfect code (with pretty linear history graphs and GNU
compliant commit messages!) without a desire to actually ship
anything.

So, what are the goals in this group?

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: development goals (was: [PATCH] Avoid `SCM_VALIDATE_LIST ()')

[Neil Jerram]

2008/9/7 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> OK - I will admit that interpreter/GC hacking is cool, but on the
> downside, when I try to do anything, the intertia/resistance I feel in
> the community here is a big turnoff for me.

Do you mean regarding releases (as you say more on below)?  Or/also
the mailing list dynamic/responsiveness?  Anything else?

>> FWIW, I would like to run my code on other schemes -- not the same goal
>> as this one, but it overlaps considerably. For me, I think that the path
>> will be implementation of some scheme standard that supports modules,
>> then migrating code over to that standard. I'm not sure about R6 though.
>
> Is there a Rx/SRFI standard for modules? I always thought that module
> system(s) was one of the unspecified areas.

R6RS specifies libraries, which are similar to modules.  (But probably
much cleverer for separate compilation, and vastly more complicated in
their semantics.)

> I am probably the only person who is in both camps currently.

I've used Guile for a substantial project at work, and I use it for
various little things on my free software machines.  But it's true
that I don't have anything to compete for size/complexity with
Lilypond.

> When working with the devs here I continue to be puzzled by what the
> objectives are.  For instance, we had 5 major (stable) releases in 11
> years.  I have always wanted this rate to go up, and have tried argue
> for that, but with 1.10 (or 2.0, whatever it is called) being in
> preparation for 2.5 years at this moment, I don't see this changing.

For me, almost all of my time since becoming a maintainer has been
absorbed by working on bug fixes, largely to do with slightly odd
platforms (e.g. Mac) or architectures (e.g. ia64).  IMO it was
worthwhile to focus on such bug reports soon after they were reported,
because (i) the reporters are still around and interested enough to be
able to provide more info and test fixes, (ii) I believe that running
on more platforms will be good for the Guile community, and for Guile
applications.

Nevertheless, I have also had a rough plan in mind, which I've never
communicated before, except vaguely to Ludovic.  I believe Ludovic
disagrees with this plan, so it certainly isn't official.  It's just
what I'm thinking, and so might be part of what eventually happens.

Basically, my feeling is that Guile users have been badly burned by
major release incompatibilities in the past, and I really don't want
that to happen again.  Therefore my "straw man" plan is that

- we stay on 1.8.x for a while

- we treat "master" as a pot of goodies, which we aim incrementally to
merge across and release as part of the 1.8.x series

- in effect, therefore, we will be releasing one (or a small number
of) new feature(s) at a time - which I hope will give us the
time/space to consider and document any incompatible issues that there
may be

- we don't do a big jump to 1.10.x, by just deciding to do so at some
time (+ a bit of pretesting), because I don't feel confident that we
can properly consider and document all of the 1.8 .. 1.10
compatibility issues at once.

But #1 : as I said above, I'm pretty sure Ludovic disagrees with this!

But #2 : actually, right now I don't even know in detail what is in
master.  I plan to review that soon, and it may be that the detailed
results completely change this.

> At such a glacial pace of development, you would imagine that backward
> compatibility would not be a concern

Huh?  That makes no sense to me.

> - after all, who plans for
> compatibility over a five year span,

I believe that programmers' natural tendency is to plan for infinite
compatibility.

> yet Guile continues to support
> (by default!) the GH interface which was deprecated in 2002 (or was it
> with version 1.4 in 2000?).

There you're right.  We can and should rip GH out now.  Actually that
might make an excellent first example for documenting incompatibility.
 (Anyone who really still needs it can take on the burden of
maintaining the GH layer themselves.)

> For LilyPond (and any other package that uses Guile, eg. texmacs,
> snd), this is a problem, since we can not realistically ship anything
> that requires the latest Git/CVS version to work.  Hence, my
> improvements in LilyPond are held back by Guile's release scheme.  For
> example, I wanted to use SCM rationals for various purposes in Lily
> for a long time, but had to wait for the 1.8 release before I could do
> this.

Are there items in master now that you are particularly wanting /
waiting for?  I guess the GC is one, any others?

Regards,
        Neil

Re: development goals

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> 2008/9/7 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>> OK - I will admit that interpreter/GC hacking is cool, but on the
>> downside, when I try to do anything, the intertia/resistance I feel in
>> the community here is a big turnoff for me.
> 
> Do you mean regarding releases (as you say more on below)?  Or/also
> the mailing list dynamic/responsiveness?  Anything else?

For a large patch (like the disputed GC patch), I got criticism of the
process I used to push it and complaints that it had multiple fixes
collated together. I was expecting criticism about what it changed,
i.e. I was hoping for more insightful comments.  It's hard to take
criticism seriously if it is only about cosmetics.

Also, the general idea that patches can only be committed if they are
'perfect' is not conducive to more rapid development.  I was rather
shocked that the idea of rolling back the change was considered a
better option than adding further fixes on top of it.

For example, there was the issue of x86_64 being broken by the
asserts.  I read complaints on the list, I got scolded at by Ludovic,
and a week later the code was still there.  I posted a proposed patch
(a single #ifdef!), to which I didn't receive a single comment.  When
I finally committed, I got a complaint that the commit message did not
have the right formatting.

Apparently:

- Rolling back a patch is preferred over fixing actual problems.

- Nobody has enough initiative to put a single strategic #ifdef in the
  code.

- If someone finally does take initiative, it's only ok if it is
  perfect.

I try not to goof up when pushing lilypond patches, but I do, up to
committing code that does not compile (yes, sue me).  When that
happens, generally people push simple fixes - there are 24 people with
push access, of whom 16 or so are active.

The people that push generally ask for review if they are unsure of
what they are doing, but when they feel certain, they do without
asking; I like that, because I don't have enough time to police the
master branch.  At ~15 commits per day I don't have time for that.  At
times, I have to request some corrections (missing regression tests,
style issues), but that is rare, and when I do I get prompt responses,
with the perpetrators pushing fixes on their own initiative.

There also are people that I know and trust to have full competence.
For example, Joe Neeman has rewritten all of the vertical spacing code
in Lily, and I don't pretend to judge or really understand his code
when he pushes.

You might construe that I would like to turn Guile development into
LilyPond development.  That is not necessarily the case, but I keep
misunderstanding what people expect in this community.  I am assuming
that developers in general are interested in a more lively and more
rapid evolution of Guile, but everytime I see habits and policies that
seem contrary to that goal.

>>> FWIW, I would like to run my code on other schemes -- not the same goal
>>> as this one, but it overlaps considerably. For me, I think that the path
>>> will be implementation of some scheme standard that supports modules,
>>> then migrating code over to that standard. I'm not sure about R6 though.
>> Is there a Rx/SRFI standard for modules? I always thought that module
>> system(s) was one of the unspecified areas.
> 
> R6RS specifies libraries, which are similar to modules.  (But probably
> much cleverer for separate compilation, and vastly more complicated in
> their semantics.)

Hmm .. curious, I thought one of the objectives of Scheme was simplicity.

>> When working with the devs here I continue to be puzzled by what the
>> objectives are.  For instance, we had 5 major (stable) releases in 11
>> years.  I have always wanted this rate to go up, and have tried argue
>> for that, but with 1.10 (or 2.0, whatever it is called) being in
>> preparation for 2.5 years at this moment, I don't see this changing.
> 
> For me, almost all of my time since becoming a maintainer has been
> absorbed by working on bug fixes, largely to do with slightly odd
> platforms (e.g. Mac) or architectures (e.g. ia64).  IMO it was
> worthwhile to focus on such bug reports soon after they were reported,
> because (i) the reporters are still around and interested enough to be
> able to provide more info and test fixes, (ii) I believe that running
> on more platforms will be good for the Guile community, and for Guile
> applications.

FWIW, I am shipping lilypond cross compiled on linux (ppc, x86_64, x86)
darwin (ppc, x86), mingw and freebsd (x86, x86_64). The stable release is
mostly working for that.

> Basically, my feeling is that Guile users have been badly burned by
> major release incompatibilities in the past, and I really don't want
> that to happen again.  Therefore my "straw man" plan is that

If anything, you should listen to your current users.  If you don't
listen to your current users, they will leave, and you won't be left
with any.

I'm one of the current users, and compatibility is the least of my
concerns.

But don't take my word. You should go out and ask other users too.  I
remember talking to Joris vd Hoeven (texmacs) several years ago, and his
complaint was that GUILE was very slow.  I didn't hear him mention
compatibility issues once

> - we stay on 1.8.x for a while
> [..]

>> At such a glacial pace of development, you would imagine that backward
>> compatibility would not be a concern
> 
> Huh?  That makes no sense to me.

Small projects don't live long enough to span 2 incompatible GUILE
releases.  The projects that do live long enough are few.  (LilyPond &
gnucash come to mind).

>> - after all, who plans for
>> compatibility over a five year span,
> 
> I believe that programmers' natural tendency is to plan for infinite
> compatibility.
> 
>> yet Guile continues to support
>> (by default!) the GH interface which was deprecated in 2002 (or was it
>> with version 1.4 in 2000?).
> 
> There you're right.  We can and should rip GH out now.  Actually that
> might make an excellent first example for documenting incompatibility.
>  (Anyone who really still needs it can take on the burden of
> maintaining the GH layer themselves.)

I probably wouldn't bother too much with documenting incompatibility;
bumping the version number to 2.0 is an easier way to deal with that.
Then again, as noted before, I am confrontational.

>> For LilyPond (and any other package that uses Guile, eg. texmacs,
>> snd), this is a problem, since we can not realistically ship anything
>> that requires the latest Git/CVS version to work.  Hence, my
>> improvements in LilyPond are held back by Guile's release scheme.  For
>> example, I wanted to use SCM rationals for various purposes in Lily
>> for a long time, but had to wait for the 1.8 release before I could do
>> this.
> 
> Are there items in master now that you are particularly wanting /
> waiting for?  I guess the GC is one, any others?

At the moment the GC fixes are one thing. Maybe I should look into 
backporting them, but the changes will be somewhat large.  

There is nothing really significant in the tree that I need desparately,
but I did contribute some features (a hook for memoize symbol) that I 
believe did not make 1.8.  I used those for measuring coverage of the
lilypond test suite.

Then again, with all the back & forth porting of changes between 1.8
and head, it's difficult to tell what is in 1.8 and what is not.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: development goals

[Ludovic Courtès]

Hi Han-Wen,

You're confrontational, indeed.

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> - Rolling back a patch is preferred over fixing actual problems.

What makes you say so?

> - Nobody has enough initiative to put a single strategic #ifdef in the
>   code.

To me, it looks like the "strategic #if 0" was a way of admitting that
we know our code is broken, we don't know why, and we don't want to
investigate that ATM but we might eventually do that if we have time.
So no, I didn't feel that happy with this.

> - If someone finally does take initiative, it's only ok if it is
>   perfect.

Yeah, that "#if 0" was just per-fect, thank you very much.

I have the impression that I'm under attack.  ;-)  It turns out that I'm
working on Guile in my spare time, which is scarce.  Surely I could do
better work if only I spent more time on Guile, I could take more
initiatives because I would be confident that if I do break something I
can work something out.

> You might construe that I would like to turn Guile development into
> LilyPond development.  That is not necessarily the case, but I keep
> misunderstanding what people expect in this community.  I am assuming
> that developers in general are interested in a more lively and more
> rapid evolution of Guile, but everytime I see habits and policies that
> seem contrary to that goal.

How many people fix bugs reported to `bug-guile'?  Believe me, spending
time doing this makes you feel reluctant to large unmotivated changes.

> Then again, with all the back & forth porting of changes between 1.8
> and head, it's difficult to tell what is in 1.8 and what is not.

Surely you'll enjoy it: we have an old-fashioned tradition of updating
`NEWS' when changing something in a branch!  :-)

Thanks,
Ludo'.

Re: development goals

[Han-Wen Nienhuys]

Ludovic Courtès escreveu:
>> You might construe that I would like to turn Guile development into
>> LilyPond development.  That is not necessarily the case, but I keep
>> misunderstanding what people expect in this community.  I am assuming
>> that developers in general are interested in a more lively and more
>> rapid evolution of Guile, but everytime I see habits and policies that
>> seem contrary to that goal.
> 
> How many people fix bugs reported to `bug-guile'?  Believe me, spending
> time doing this makes you feel reluctant to large unmotivated changes.

Good point.  I've just added myself to that list. 

>> Then again, with all the back & forth porting of changes between 1.8
>> and head, it's difficult to tell what is in 1.8 and what is not.
> 
> Surely you'll enjoy it: we have an old-fashioned tradition of updating
> `NEWS' when changing something in a branch!  :-)

Well, yes, but we also have many commits that are identified as 

  "Changes from Arch/CVS synchronization" 

and 

  "merge from 1.8" 

I tend to look at development history with gitk.  I realize these 
commits are from the CVS era, but it makes me loose track of what
is happening where.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: development goals

[Andy Wingo]

Hi,

On Mon 08 Sep 2008 12:16, ludo@gnu.org (Ludovic Courtès) writes:

> Han-Wen Nienhuys <hanwen@xs4all.nl> writes:
>
>> - Nobody has enough initiative to put a single strategic #ifdef in the
>>   code.
>
> To me, it looks like the "strategic #if 0" was a way of admitting that
> we know our code is broken, we don't know why, and we don't want to
> investigate that ATM but we might eventually do that if we have time.
> So no, I didn't feel that happy with this.

I was not happy with this either.

>> - If someone finally does take initiative, it's only ok if it is
>>   perfect.

It's great that you're working on this stuff! But it should have been
pushed to a branch. The thing is, it really *does* need to be perfect.
Maybe not at first push, but within a couple weeks of being merged to
mainline. My fear was that since Guile hackers have so little time, in
general, that you would push something broken in corner cases, then walk
off -- not a concern specific to any one person.

It's good that you are sticking around to iron out the bugs.

Andy
-- 
http://wingolog.org/

Re: development goals

[Ludovic Courtès]

Hey!

"Neil Jerram" <neiljerram@googlemail.com> writes:

> For me, almost all of my time since becoming a maintainer has been
> absorbed by working on bug fixes, largely to do with slightly odd
> platforms (e.g. Mac) or architectures (e.g. ia64).  IMO it was
> worthwhile to focus on such bug reports soon after they were reported,
> because (i) the reporters are still around and interested enough to be
> able to provide more info and test fixes, (ii) I believe that running
> on more platforms will be good for the Guile community, and for Guile
> applications.

Same here.  But everyone is welcome to help fix bugs!  :-)

> Basically, my feeling is that Guile users have been badly burned by
> major release incompatibilities in the past, and I really don't want
> that to happen again.  Therefore my "straw man" plan is that
>
> - we stay on 1.8.x for a while

Which IMO means fixing portability bugs and the likes.

> - we treat "master" as a pot of goodies, which we aim incrementally to
> merge across and release as part of the 1.8.x series

The problem is that some of them might be subtly incompatible, mostly
because a lot of internals have been exposed and actually used.

I think it's good to have API and possibly ABI-compatibility within a
major release, so that "1.8.x" really means something, for any value of
`x'; requiring "x >= something" is acceptable IMO (we already have this,
e.g., with modules that got added in 1.8), but "a <= x <= b" isn't.

> - we don't do a big jump to 1.10.x, by just deciding to do so at some
> time (+ a bit of pretesting), because I don't feel confident that we
> can properly consider and document all of the 1.8 .. 1.10
> compatibility issues at once.

I agree that we should reduce the gap between any two major releases.

> But #1 : as I said above, I'm pretty sure Ludovic disagrees with this!

It's not all black & white.  ;-)

> I believe that programmers' natural tendency is to plan for infinite
> compatibility.

+1.

(That is especially true in Guile land where many projects are small and
developed only on people's spare time, whom you can't expect to dedicate
time switching APIs.)

> There you're right.  We can and should rip GH out now.  Actually that
> might make an excellent first example for documenting incompatibility.
>  (Anyone who really still needs it can take on the burden of
> maintaining the GH layer themselves.)

IMO, if it doesn't cost anything to keep it (beside `.so' size), let's
keep it.

Thanks,
Ludo'.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/4 Andy Wingo <wingo@pobox.com>:
>
> I think it makes a *lot* of sense to compile elisp to the VM. I don't
> plan on doing so myself, but if the VM gets good enough, it could be
> enhanced with the instructions that elisp needs, if any, and it would be
> possible to run emacs lisp code, and possibly even emacs itself, on
> guile.

That sounds good for elisp code.  For "even emacs itself", the
obstacle is implementing the vast crowd of emacs primitives...

> I don't know where the boundary lies regarding C primitives, though. I
> think we'll eventually want to make VM-implemented functions as fast or
> faster than the C ones, through a tracing JIT or something. So you could
> make elisp reference different C primitives, or implement its primitives
> in elisp (or scheme, or whatever), or make our C primitives do both.

Currently, in lang/elisp/*, a handful of emacs primitives are
implemented in Scheme.  I suspect the only sane long term solution
would involve reuse of the Emacs code - which then would make the
lang/elisp/* experiment converge with Ken Raeburn's experiment.

Regards,
       Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/1 Ludovic Courtès <ludo@gnu.org>:
> Hello,
>
> This is a followup to this discussion:
>
>  http://thread.gmane.org/gmane.lisp.guile.devel/7194
>
> The attached patch changes several list-related functions

reverse!, memq, memv, member, filter, filter!
SRFI-1: concatenate, concatenate!, member, remove, remove!

> so that they
> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).

I'm afraid I don't get your rationale, because all these functions are
O(n) anyway.  (For reverse*, filter* and concatenate* I believe this
is obvious.  For mem* and remove*, they should always be O(n) in
practice because it would be stupid to design a list structure where
the element being looked for or removed was not equally likely to be
anywhere along the list.)

I know you gave an example in the above-referenced thread, but IMO
that was a pathological one.  Did you find the use of
SCM_VALIDATE_LIST () causing a problem in real practical code?

> A side-effect (besides performance improvements) is that all these
> functions will now happily traverse circular lists, and will silently
> deal with dotted lists.  This is acceptable behavior IMO.

Are you sure about traversing circular lists?  From my reading of your
patch, I would expect:

(memq 'not-in-the-list some-circular-list)
=>
(don't know, still waiting...)

:-)

What do reverse* do on a circular list?  What do concatenate* do?

There are a few more specific comments below, but on balance, at the
moment, I'm seeing more disadvantages here than benefit...

Regards,
          Neil

> diff --git a/NEWS b/NEWS
> index c2bed17..cfcd43b 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -56,6 +56,13 @@ When you use GDS to evaluate Scheme code from Emacs, you can now use
>  This makes these internal functions technically not callable from
>  application code.
>
> +** Remove argument type checking with `list?' in some list-related functions

It's easy to read that as just "Remove argument type checking".  Could
we say "Improve scalability of some list-related functions" instead,
and leave the type checking detail to the following para?

> +
> +Several list-related functions (e.g., `memq', `list-copy', etc.) used
> +R5RS `list?' to validate their arguments.  However, `list?' has linear
> +complexity, so these functions have been changed to not resort to
> +`list?'.
> +
>  ** `guile-config link' now prints `-L$libdir' before `-lguile'
>  ** Fix memory corruption involving GOOPS' `class-redefinition'
>  ** Fix build issue on Tru64 and ia64-hp-hpux11.23 (`SCM_UNPACK' macro)
> diff --git a/libguile/list.c b/libguile/list.c
> index a1a79a4..8b0a2e4 100644
> --- a/libguile/list.c
> +++ b/libguile/list.c
> @@ -1,4 +1,4 @@
> -/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004
> +/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004,2008
>   * Free Software Foundation, Inc.
>   *
>   * This library is free software; you can redistribute it and/or
> @@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
>  	    "@code{reverse!}")
>  #define FUNC_NAME s_scm_reverse_x
>  {
> -  SCM_VALIDATE_LIST (1, lst);
>    if (SCM_UNBNDP (new_tail))
>      new_tail = SCM_EOL;
>    else
> -    SCM_VALIDATE_LIST (2, new_tail);
> +    SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail),
> +		new_tail, 2, FUNC_NAME);

Why does new_tail need to satisfy this condition?  Please either add a
comment to explain, or just remove.

>    while (!SCM_NULL_OR_NIL_P (lst))
>      {
> -      SCM old_tail = SCM_CDR (lst);
> +      SCM old_tail;
> +
> +      SCM_VALIDATE_CONS (1, lst);
> +
> +      old_tail = SCM_CDR (lst);
>        SCM_SETCDR (lst, new_tail);
>        new_tail = lst;
>        lst = old_tail;

Note that if SCM_VALIDATE_CONS fails half way through the "list", the
input list will have been destructively modified such that it is
neither the same as when it started, nor a complete reversed list.  Is
that a concern?

> @@ -546,7 +550,8 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
>    SCM * fill_here;
>    SCM from_here;
>
> -  SCM_VALIDATE_LIST (1, lst);
> +  SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst),
> +	      lst, 1, FUNC_NAME);

Why impose this condition specifically on the head of the provided
list?  Please either explain or remove.

>
>    newlst = SCM_EOL;
>    fill_here = &newlst;
> @@ -613,8 +618,13 @@ SCM_DEFINE (scm_memq, "memq", 2, 0, 0,
>  	    "returned.")
>  #define FUNC_NAME s_scm_memq
>  {
> -  SCM_VALIDATE_LIST (2, lst);
> -  return scm_c_memq (x, lst);
> +  for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
> +    {
> +      SCM_VALIDATE_CONS (2, lst);
> +      if (scm_is_eq (SCM_CAR (lst), x))
> +	return lst;
> +    }
> +  return SCM_BOOL_F;
>  }
>  #undef FUNC_NAME
>
> @@ -629,9 +639,9 @@ SCM_DEFINE (scm_memv, "memv", 2, 0, 0,
>  	    "returned.")
>  #define FUNC_NAME s_scm_memv
>  {
> -  SCM_VALIDATE_LIST (2, lst);
>    for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
>      {
> +      SCM_VALIDATE_CONS (2, lst);
>        if (! scm_is_false (scm_eqv_p (SCM_CAR (lst), x)))
>  	return lst;
>      }
> @@ -650,9 +660,9 @@ SCM_DEFINE (scm_member, "member", 2, 0, 0,
>  	    "empty list) is returned.")
>  #define FUNC_NAME s_scm_member
>  {
> -  SCM_VALIDATE_LIST (2, lst);
>    for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst))
>      {
> +      SCM_VALIDATE_CONS (2, lst);
>        if (! scm_is_false (scm_equal_p (SCM_CAR (lst), x)))
>  	return lst;
>      }
> @@ -884,9 +894,11 @@ SCM_DEFINE (scm_filter, "filter", 2, 0, 0,
>    SCM walk;
>    SCM *prev;
>    SCM res = SCM_EOL;
> +
>    SCM_ASSERT (call, pred, 1, FUNC_NAME);
> -  SCM_VALIDATE_LIST (2, list);
> -
> +  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
> +	      list, 2, FUNC_NAME);

Same comment as above.

> +
>    for (prev = &res, walk = list;
>         scm_is_pair (walk);
>         walk = SCM_CDR (walk))
> @@ -910,9 +922,11 @@ SCM_DEFINE (scm_filter_x, "filter!", 2, 0, 0,
>    scm_t_trampoline_1 call = scm_trampoline_1 (pred);
>    SCM walk;
>    SCM *prev;
> +
>    SCM_ASSERT (call, pred, 1, FUNC_NAME);
> -  SCM_VALIDATE_LIST (2, list);
> -
> +  SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list),
> +	      list, 2, FUNC_NAME);

Same comment as above.

> +
>    for (prev = &list, walk = list;
>         scm_is_pair (walk);
>         walk = SCM_CDR (walk))

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hi Neil,

"Neil Jerram" <neiljerram@googlemail.com> writes:

>> so that they
>> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
>
> I'm afraid I don't get your rationale, because all these functions are
> O(n) anyway.

You're right, but it's always better to traverse the list once rather
than twice.  :-)

It doesn't feel right to impose that overhead "just" for the sake of
type-checking.

Type-checking using `list?' in these cases was actually overzealous
since neither RnRS nor SRFI-1 require it.

Note: We could change these functions to still diagnose what `list?'
diagnoses while avoiding `SCM_VALIDATE_LIST ()' such that only one list
traversal is done.  It boils down to implementing the tortoise and the
hare in each function, as shown in the `list-copy' patch.

> Did you find the use of SCM_VALIDATE_LIST () causing a problem in real
> practical code?

What does that mean?  Real practical code using `memq' behaves just as
if it called `memq' twice, that's it.  Whether that is a "problem"
depends on how often that happens, how long the list is, and how long
you're willing to wait.  :-)

>> A side-effect (besides performance improvements) is that all these
>> functions will now happily traverse circular lists, and will silently
>> deal with dotted lists.  This is acceptable behavior IMO.
>
> Are you sure about traversing circular lists?  From my reading of your
> patch, I would expect:
>
> (memq 'not-in-the-list some-circular-list)
> =>
> (don't know, still waiting...)

Yes, that's what I meant by "happily traverse circular lists".  :-)

> What do reverse* do on a circular list?  What do concatenate* do?

They keep reversing or concatenating---and it takes long!  :-)

> There are a few more specific comments below, but on balance, at the
> moment, I'm seeing more disadvantages here than benefit...

Again, if the disadvantage is that circular lists are not diagnosed, we
can add tortoise-and-hare protection to each function while still
avoiding double traversal.  I'm not sure it's worth it, though.

>> +** Remove argument type checking with `list?' in some list-related functions
>
> It's easy to read that as just "Remove argument type checking".  Could
> we say "Improve scalability of some list-related functions" instead,
> and leave the type checking detail to the following para?

Right.

>> @@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
>>  	    "@code{reverse!}")
>>  #define FUNC_NAME s_scm_reverse_x
>>  {
>> -  SCM_VALIDATE_LIST (1, lst);
>>    if (SCM_UNBNDP (new_tail))
>>      new_tail = SCM_EOL;
>>    else
>> -    SCM_VALIDATE_LIST (2, new_tail);
>> +    SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail),
>> +		new_tail, 2, FUNC_NAME);
>
> Why does new_tail need to satisfy this condition?  Please either add a
> comment to explain, or just remove.

It's a mechanical change: the code used to check for a proper list, I
just changed it to check for a list (i.e., '() or a pair).

> Note that if SCM_VALIDATE_CONS fails half way through the "list", the
> input list will have been destructively modified such that it is
> neither the same as when it started, nor a complete reversed list.  Is
> that a concern?

(I think that was `reverse!'.)

Portable RnRS code and code written without looking at `list.c' must use
`list?' before calling `reverse!' to protect from such situations.  So,
to me, that's not a concern.

Now, one could argue that there's code out there that relies on Guile's
undocumented over-restriction on input arguments.  That's always
possible, but hopefully sufficiently rare.

>> @@ -546,7 +550,8 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0,
>>    SCM * fill_here;
>>    SCM from_here;
>>
>> -  SCM_VALIDATE_LIST (1, lst);
>> +  SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst),
>> +	      lst, 1, FUNC_NAME);
>
> Why impose this condition specifically on the head of the provided
> list?

So that "(list-copy 1)" raises an exception, rather than being silently
ignored (as is the case with `list-copy' from `srfi-1.c').  Again, a
mechanical change.

Thanks,
Ludo'.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

Hi Ludovic,

I'm sorry but I'm still really struggling to see how this change helps us...

2008/9/1 Ludovic Courtès <ludo@gnu.org>:
> Hi Neil,
>
> "Neil Jerram" <neiljerram@googlemail.com> writes:
>
>>> so that they
>>> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
>>
>> I'm afraid I don't get your rationale, because all these functions are
>> O(n) anyway.
>
> You're right, but it's always better to traverse the list once rather
> than twice.  :-)

Not necessarily.  It depends what happens inside the loop, on each
iteration, and whether the iteration time is significant in comparison
with that.

> It doesn't feel right to impose that overhead "just" for the sake of
> type-checking.

What overhead?  (Quantifiably, I mean.)

Another slight concern is that this change seems to me to take us
further away from one of Mikael's possible ideas for the future: being
able to completely _remove_ a lot of the typechecking that we
currently do, because we instead carry around some representation of
what we already know about arguments.

I don't believe anyone's worked this all out yet, but, for example, if
the arg to scm_reverse() was generated by some other function that is
known only to produce proper lists, then the arg might be represented
as (<proper-list> . the-actual-list), and obviously then the
SCM_VALIDATE_LIST in scm_reverse() can be completely skipped.  If the
validation code is interleaved with the actually-doing-something code,
it becomes more difficult to skip (in some hypothetical future).

> Type-checking using `list?' in these cases was actually overzealous
> since neither RnRS nor SRFI-1 require it.

OK, but on its own I don't think this is a strong reason for change.

> Note: We could change these functions to still diagnose what `list?'
> diagnoses while avoiding `SCM_VALIDATE_LIST ()' such that only one list
> traversal is done.  It boils down to implementing the tortoise and the
> hare in each function, as shown in the `list-copy' patch.

That's pretty horrible as far as code complexity and maintenance are concerned!

>> Did you find the use of SCM_VALIDATE_LIST () causing a problem in real
>> practical code?
>
> What does that mean?

Did you (or someone else) see a performance problem in a real,
moderately complex application, which you analyzed and discovered to
be significantly caused by these SCM_VALIDATE_LIST() invocations?

> Real practical code using `memq' behaves just as
> if it called `memq' twice, that's it.

Yes (or perhaps 3 or more times...).  And Scheme is slower than C, so
should we all drop Scheme?

This kind of argument is premature optimization, which is well known
to be misguided.  (Isn't it?)

>>> A side-effect (besides performance improvements) is that all these
>>> functions will now happily traverse circular lists, and will silently
>>> deal with dotted lists.  This is acceptable behavior IMO.
>>
>> Are you sure about traversing circular lists?  From my reading of your
>> patch, I would expect:
>>
>> (memq 'not-in-the-list some-circular-list)
>> =>
>> (don't know, still waiting...)
>
> Yes, that's what I meant by "happily traverse circular lists".  :-)

!  :-)

Do we really need to continue this discussion?  I just don't see
anything helpful about this change.

But perhaps I'm misunderstanding.  Surely there must be _some_ clear
benefit, which motivated you to work on this - can you say what that
was?

I guess I should just finish off the email though, for completeness...

>> Why does new_tail need to satisfy this condition?  Please either add a
>> comment to explain, or just remove.
>
> It's a mechanical change: the code used to check for a proper list, I
> just changed it to check for a list (i.e., '() or a pair).

I'm afraid this doesn't make sense to me.  A list isn't "'() or a pair".

>> Note that if SCM_VALIDATE_CONS fails half way through the "list", the
>> input list will have been destructively modified such that it is
>> neither the same as when it started, nor a complete reversed list.  Is
>> that a concern?
>
> (I think that was `reverse!'.)

Yes, indeed, sorry.

> Portable RnRS code and code written without looking at `list.c' must use
> `list?' before calling `reverse!' to protect from such situations.  So,
> to me, that's not a concern.
>
> Now, one could argue that there's code out there that relies on Guile's
> undocumented over-restriction on input arguments.  That's always
> possible, but hopefully sufficiently rare.

I agree that one can't always cater for every bit of code of there,
but I need a better reason to risk breakage than I'm seeing at the
moment.

Regards,
     Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hello!

"Neil Jerram" <neiljerram@googlemail.com> writes:

> I'm sorry but I'm still really struggling to see how this change helps us...

Yes, I see...  ;-)

I'm taking it the other way: I can't see how one can argue for unneeded
run-time overhead.

> 2008/9/1 Ludovic Courtès <ludo@gnu.org>:

>> You're right, but it's always better to traverse the list once rather
>> than twice.  :-)
>
> Not necessarily.  It depends what happens inside the loop, on each
> iteration, and whether the iteration time is significant in comparison
> with that.

I'd say it's better regardless of what's inside the loop.

Sure, one may argue that `memq' is rarely used with million-of-element
lists anyway, because other methods would be used in such situations
(hash tables, etc.).  But that's not necessarily the case with
`reverse', `partition', etc.

> What overhead?  (Quantifiably, I mean.)

In terms of profile dumps, a full run of the test suite under Callgrind
reveals that `scm_ilength ()' is *not* in the top 10.  But hey, one
could surely come up with a Real World(TM) application that does a lot
of list processing and is measurably impacted by that double traversal.

> I don't believe anyone's worked this all out yet, but, for example, if
> the arg to scm_reverse() was generated by some other function that is
> known only to produce proper lists, then the arg might be represented
> as (<proper-list> . the-actual-list), and obviously then the
> SCM_VALIDATE_LIST in scm_reverse() can be completely skipped.  If the
> validation code is interleaved with the actually-doing-something code,
> it becomes more difficult to skip (in some hypothetical future).

How would you remove those checks from compiled code like `list.o'?

Guile-VM, OTOH, may have clear opportunities to optimize away certain
cases at compilation time.

> Do we really need to continue this discussion?

Maybe not.

To be honest, I didn't expect I'd have to argue about this in the first
place.  I see it as a (maybe small, application-dependent) benefit,
while I have the impression that you regard it solely as a "possible
breakage" and as "code churning".  Probably we disagree because we don't
value the same things here.

Thanks,
Ludo'.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Mikael Djurfeldt]

2008/9/1 Ludovic Courtès <ludo@gnu.org>:
>> Are you sure about traversing circular lists?  From my reading of your
>> patch, I would expect:
>>
>> (memq 'not-in-the-list some-circular-list)
>> =>
>> (don't know, still waiting...)
>
> Yes, that's what I meant by "happily traverse circular lists".  :-)

From my experience, there was a huge improvement in scheme program
development time when we moved to real type-checking of lists from the
kind of type-checking you seem to want to re-introduce. It's much
easier to debug code if you can assume that hangs are not due to
circular data structures.

Having been part of Guile development for some time, it's sad to see
how much work is put into changing code back and forth due to
vacillating development goals.  It's apparent how important it is to
have a written development policy with design decisions and
motivations.  Probably a lot of that should also be put directly into
the code in the form of comments.

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Mikael Djurfeldt escreveu:
>> Yes, that's what I meant by "happily traverse circular lists".  :-)

> Having been part of Guile development for some time, it's sad to see
> how much work is put into changing code back and forth due to
> vacillating development goals.  It's apparent how important it is to
> have a written development policy with design decisions and
> motivations.  Probably a lot of that should also be put directly into
> the code in the form of comments.

+1 

I am participating in GUILE since it is a foundation of LilyPond.  As 
far as I am concerned, it should be fast, bug-free, standards-compliant
and should not have any code that is so complex that it will bitrot when 
its developer takes off.

That is why I am bothered by the half-working elisp support: my 
impression is that is not really used, so once Neil stops doing his
job, GUILE will be left with a bunch of weird code that noone knows
how to deal with.

All this also makes me wonder why there are no  Gnucash developers 
here, since I recall they actually do use GUILE for a lot of stuff.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> I am participating in GUILE since it is a foundation of LilyPond.  As
> far as I am concerned, it should be fast, bug-free, standards-compliant
> and should not have any code that is so complex that it will bitrot when
> its developer takes off.

Agreed - modulo that sometimes complexity is useful/needed, and in
such situations it can be made acceptable by sufficient commenting.

> That is why I am bothered by the half-working elisp support: my
> impression is that is not really used, so once Neil stops doing his
> job, GUILE will be left with a bunch of weird code that noone knows
> how to deal with.

I don't think the elisp support is complex, but I've made a note to
review it and add comments where that would be useful.

> All this also makes me wonder why there are no  Gnucash developers
> here, since I recall they actually do use GUILE for a lot of stuff.

I'm afraid to say that I believe they are moving away from Guile.  I
think their reasons are different, though: the (perceived) complexity
of the g-wrap workflow, and new core developers not liking Scheme as a
language.

Regards,
        Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/7 Mikael Djurfeldt <mikael@djurfeldt.com>:
>
> >From my experience, there was a huge improvement in scheme program
> development time when we moved to real type-checking of lists from the
> kind of type-checking you seem to want to re-introduce. It's much
> easier to debug code if you can assume that hangs are not due to
> circular data structures.

Thanks for that data point!

> Having been part of Guile development for some time, it's sad to see
> how much work is put into changing code back and forth due to
> vacillating development goals.

(Oh dear, this seems to be my week for arguing with everybody... :-))

It is?  I am not aware of any other recent changes that fall into this
category, are you?

(It is precisely because this change is unique, IMO, in churning code
for no benefit, so I am getting so heavy about it! :-))

> It's apparent how important it is to
> have a written development policy with design decisions and
> motivations.

Apart from the VM work, there has been little development recently
that is big enough to merit or need an upfront design.  I would say we
have been mostly focussed for the last year on stability and
cross-platform support.

> Probably a lot of that should also be put directly into
> the code in the form of comments.

Agreed there!  The Guile code could use a lot more comments.

         Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> 2008/9/1 Ludovic Courtès <ludo@gnu.org>:
>> Hello,
>>
>> This is a followup to this discussion:
>>
>>  http://thread.gmane.org/gmane.lisp.guile.devel/7194
>>
>> The attached patch changes several list-related functions
> 
> reverse!, memq, memv, member, filter, filter!
> SRFI-1: concatenate, concatenate!, member, remove, remove!
> 
>> so that they
>> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
> 
> I'm afraid I don't get your rationale, because all these functions are
> O(n) anyway.  (For reverse*, filter* and concatenate* I believe this
> is obvious.  For mem* and remove*, they should always be O(n) in
> practice because it would be stupid to design a list structure where
> the element being looked for or removed was not equally likely to be
> anywhere along the list.)

All these functions are O(n), but by prefixing the list check
you're doubling the running time (eg. in the case of reverse!). 

If you are doing memq? for something you already know to 
somewhere in front of the list, the list? check will slow
it down much worse.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Neil Jerram]

2008/9/2 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>
> If you are doing memq? for something you already know to
> somewhere in front of the list [...]

Why would you do that?  In two senses:

1. I know memq gives you the tail of the list, but I usually use its
result only as a true/false value Why would run use memq like that in
a situation where you already know that it will give you true?

2. It feels unusual to me to have a long list, but in which certain
kinds of values are known always to be near the front.  That sounds
like something that should really be represented as two (or more)
separate lists.

Have you observed this (the current usage of SCM_VALIDATE_LIST) as a
performance problem in practice?

Regards,
         Neil

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> 2008/9/2 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>> If you are doing memq? for something you already know to
>> somewhere in front of the list [...]
> 
> Why would you do that?  In two senses:
> 
> 1. I know memq gives you the tail of the list, but I usually use its
> result only as a true/false value Why would run use memq like that in
> a situation where you already know that it will give you true?
> 
> 2. It feels unusual to me to have a long list, but in which certain
> kinds of values are known always to be near the front.  That sounds
> like something that should really be represented as two (or more)
> separate lists.
> 
> Have you observed this (the current usage of SCM_VALIDATE_LIST) as a
> performance problem in practice?

No, but it feels strange to me that a function whose intrinsic function
does not require O(n) behavior, does require it in all cases.

However, I find Mikael's argument that it complicates programming a lot 
persuasive.

-- 
 Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Clinton Ebadi]

Han-Wen Nienhuys <hanwen@xs4all.nl> writes:

> Neil Jerram escreveu:
>> 2008/9/2 Han-Wen Nienhuys <hanwen@xs4all.nl>:
>>> If you are doing memq? for something you already know to
>>> somewhere in front of the list [...]
>> 
>> Why would you do that?  In two senses:
>> 
>> 1. I know memq gives you the tail of the list, but I usually use its
>> result only as a true/false value Why would run use memq like that in
>> a situation where you already know that it will give you true?
>> 
>> 2. It feels unusual to me to have a long list, but in which certain
>> kinds of values are known always to be near the front.  That sounds
>> like something that should really be represented as two (or more)
>> separate lists.
>> 
>> Have you observed this (the current usage of SCM_VALIDATE_LIST) as a
>> performance problem in practice?
>
> No, but it feels strange to me that a function whose intrinsic function
> does not require O(n) behavior, does require it in all cases.
>
> However, I find Mikael's argument that it complicates programming a lot 
> persuasive.

How about something like (obviously better and in C):

(define (detect-cycle lst fn)
  (let ((get-hare (lambda (lst)
		    (if (and (pair? lst) (pair? (cdr lst)))
			(cddr lst)
			#f)))
	(get-tortoise (lambda (lst)
			(if (pair? lst)
			    (cdr lst)
			    (error "End of list hit")))))
    (let detect ((tortoise lst)
		 (hare (get-hare lst)))
      (fn tortoise)
      (cond ((eq? tortoise hare)
	     (error "cycle detected"))
	    (else (detect (get-tortoise tortoise)
			  (get-hare hare)))))))

;;; example

(define (cyclic-memq x lst)
  ;; Obviously a real version would want to catch an exception here
  ;; and return the proper value
  (detect-cycle lst (lambda (sublist)
		      (if (eq? (car sublist) x)
			  (error "x found")))))

In C the only burden would be defining one-use helper functions and a
struct (or perhaps just a Scheme list since there would be at most one
or two values each faked closure would need) for storing any data they
would need. It would be a tad bit ugly, but would neatly (as neatly as
can be done in C at least) allow every list traversing primitive
function to avoid cycles (and still work on cyclic lists where the
item was actually there) without traversing the entire list.

The question then becomes whether the overhead of a bunch of indirect
function calls would be an issue. Asymptotically this wouldn't matter
(but neither does potentially traversing the entire list twice except
that now your best and worst case are both N), but in reality with
average list length and all...

Perhaps a macro could be used instead (is it possible to pass entire
blocks of code to a macro using something like CYCLE_DETECTING({
.... code ... }) in C?). It would be a very hairy macro, but would
again give every list traversal primitive the ability to avoid
spinning on cyclic lists or dying at the end of improper lists without
having a separate implementation of the tortoise and hare algorithm in
every function.

-- 
          Who will tend the garden when the snake swallows the light?          
         Who will eat the decay when the worms have lost their sight?          
           Who will rape the weak when there's nothing left to gain?           
             Who will till the soil of these barren black remains?             

Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Ludovic Courtès]

Hi,

Clinton Ebadi <clinton@unknownlamer.org> writes:

> Perhaps a macro could be used instead (is it possible to pass entire
> blocks of code to a macro using something like CYCLE_DETECTING({
> .... code ... }) in C?).

Sure, something like `scm_i_for_each (element, list)' that expands to a
tortoise-and-hare test.

Thanks,
Ludo'.