Creating recursive customization types / widgets

Creating recursive customization types / widgets

[Per Abrahamsen]

Creating new widgets from existing customization type specifications
has something of a black magic feel to it, and creating widgets for
recursive datastructures is next to impossible.

Below is a new widget named "child", which should simplify both tasks
a lot.  

Background: The predefined complex widgets, i.e. the widgets that is
build from other widgets, has their types expanded at creation for
speed.  This obviously goes wrong for recursive types.  This new
"child" widget is a delayed action wrapper of an arbitrary widget,
specified in its :type argument.  The value of the :type argument will
not be expanded before it is needed, which allow for recursive
datastructures.  Since the :type argument to this widget takes exactly
the same values as the :type argument to defcustom, it will also be
useful for people who want to "name" a type for custom use.

If the datastructures is recursive, you need to gave a :match argument
as well as :type.  If not, it will simply match any values that the
type specified for :type will match.

Here is the code for the "child" widget, as well as an example of a
recursive datastructure (a binary tree of strings).  

I suggest we add the "child" widget to wid-edit.el, and document it
somewhere. 

(define-widget 'child 'default
  "Base widget for recursive datastructures.

You need to set :type to the widget type for the datastructure you
want to define, and set :match to a function that matches the
datastructure.  If the datastructure is not recursive, you don't have
to set :match."
  :format "%v"
  ;; We don't convert :type because we want to allow recursive
  ;; datastructures.  This is slow, so we should not create speed
  ;; critical widgets by deriving from this. 
  :convert-widget 'widget-value-convert-widget
  :value-create 'widget-child-value-create
  :value-delete 'widget-children-value-delete
  :value-get 'widget-child-value-get
  :value-inline 'widget-child-value-inline
  :default-get 'widget-child-default-get
  :validate 'widget-child-validate)

(defun widget-child-value-create (widget)
  "Create the child widget."
  (let ((value (widget-get widget :value))
	(type (widget-get widget :type)))
    (widget-put widget :children 
                (list (widget-create-child-value widget 
                                                 (widget-convert type)
                                                 value)))))

(defun widget-child-value-get (widget)
  ;; Get value of the child widget.
  (widget-value (car (widget-get widget :children))))

(defun widget-child-value-inline (widget)
  ;; Get value of the child widget.
  (widget-apply (car (widget-get widget :children)) :value-inline))

(defun widget-child-default-get (widget)
  ;; Get default for the child.
  (widget-default-get (car (widget-get widget :args))))

(defun widget-child-match (widget value)
  "Matches iff the child matches.
You need to overwrite you want to match recursive datastructures."
  (widget-apply (widget-convert (widget-get widget :type)) :match value))

(defun widget-child-validate (widget)
  "Valid iff the child is valid."
  (widget-apply (car (widget-get widget :children)) :validate))


(define-widget 'binary-tree-of-string 'child
  "A binary tree made of cons-cells and strings."
  :offset 4
  :match (lambda (widget value)
           (binary-tree-of-string-p value))
  :type '(menu-choice (string :tag "Leaf" :value "")
                      (cons :tag "Interior"
                            :value ("" . "") 
                            binary-tree-of-string
                            binary-tree-of-string)))

(defun binary-tree-of-string-p (object)
  "Return t if OBJECT is a binary tree of strings."
  (or (stringp object)
      (and (consp object)
           (binary-tree-of-string-p (car object))
           (binary-tree-of-string-p (cdr object)))))

;; Evaluate this to edit the buffer again.
(lisp-interaction-mode)

;; Evaluate this to get the current value.
(widget-value w)

;; Evaluate this to create and edit a test widget.
(progn 
  (setq w (widget-create 'binary-tree-of-string '("a" . (("b" . "c") . "d"))))
  (widget-setup) (widget-browse-mode))

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> (define-widget 'child 'default
>   "Base widget for recursive datastructures.
>
> You need to set :type to the widget type for the datastructure you
> want to define, and set :match to a function that matches the
> datastructure.  If the datastructure is not recursive, you don't have
> to set :match."
>   :format "%v"

This should be 

  :format "%{%t%}: %v"

to make it directly usable as a customization type.

Re: Creating recursive customization types / widgets

[Stefan Monnier]

> Below is a new widget named "child", which should simplify both tasks
> a lot.  

Neat.  I have no idea why it's called `child' and the resulting
use of `child' in (define-widget 'foo 'child ...) does not look
particularly intuitive, but I can't think of anything better either.

We should install this.

> If the datastructures is recursive, you need to gave a :match argument
> as well as :type.

Why is that ?

> If not, it will simply match any values that the
> type specified for :type will match.

Which seems like what we want.  Are there cases where it doesn't work
and if so, why not (i.e. can we fix it) ?


        Stefan

Re: Creating recursive customization types / widgets

[Richard Stallman]

    (define-widget 'child 'default
      "Base widget for recursive datastructures.

    You need to set :type to the widget type for the datastructure you
    want to define, and set :match to a function that matches the
    datastructure.  If the datastructure is not recursive, you don't have
    to set :match."

It looks like a good feature, but I can't really understand
that doc string, so it needs to be somewhat clearer.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> Neat.  I have no idea why it's called `child' and the resulting
> use of `child' in (define-widget 'foo 'child ...) does not look
> particularly intuitive, but I can't think of anything better either.

Because it has a single child widget, and the new widget basically
behave like the child, except for allowing recursion.

I called it 'recursive' and 'delayed' under development.

It is a common pattern in OOP.  Having an object that wraps another
object, delegates message to the other object, and thus acts like a
proxy.  So 'wrapper', delegator' or 'proxy' could be used as well.

> We should install this.

Yes.  It answers the most common custom/widget programming question
that I couldn't previously answer :-)

>> If the datastructures is recursive, you need to gave a :match argument
>> as well as :type.
>
> Why is that ?

Good question.  I was afraid of infinite recursion, but as long as the
widget type "eat some tokens" of the value before the recursion
starts, that doesn't happen.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Richard Stallman <rms@gnu.org> writes:

>     (define-widget 'child 'default
>       "Base widget for recursive datastructures.
>
>     You need to set :type to the widget type for the datastructure you
>     want to define, and set :match to a function that matches the
>     datastructure.  If the datastructure is not recursive, you don't have
>     to set :match."
>
> It looks like a good feature, but I can't really understand
> that doc string, so it needs to be somewhat clearer.

Most widget doc strings are much worse, but that's no excuse.

Is the following understandable?

(define-widget 'child 'default
  "Base widget for recursive datastructures.

The `child' widget will, when instantiated, contain a single inferior
widget, of the widget type specified by the :type parameter.  The
value of the `child' widget is the same as the value of the inferior
widget.  When deriving a new widget from the 'child' widget, the :type
parameter is allowed to refer to the widget currently being defined,
thus allowing recursive datastructures to be described.

The :type parameter takes the same arguments as the defcustom
parameter with the same name.

Background: Most composite widgets, i.e. widgets containing other
widgets, does not allow recursion.  That is, when you define a new
widget type, none of the inferior widgets may be of the same type you
are currently defining.

In Lisp, however, it is custom to define datastructures in terms of
themselves.  A list, for example, is defined as either nil, or a cons
cell whose cdr itself is a lisp.  The obvious way to translate this
into a widget type would be

  (define-widget 'my-list 'choice
    \"A list of sexps.\"
    :tag \"Sexp list\"
    :args '((const nil) (cons :value (nil) sexp my-list)))

Here we attempt to define my-list as a choice of either the constant
nil, or a cons-cell containing a sexp and my-lisp.  This will not work
because the `choice' widget does not allow recursion.

Using the `child' widget you can overcome this problem, as in this 
example: 

  (define-widget 'sexp-list 'child
    \"A list of sexps.\"
    :tag \"Sexp list\"
    :type '(choice (const nil) (cons :value (nil) sexp sexp-list)))"
  :format "%{%t%}: %v"

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>> If the datastructures is recursive, you need to gave a :match argument
>> as well as :type.
>
> Why is that ?
>
>> If not, it will simply match any values that the
>> type specified for :type will match.
>
> Which seems like what we want.  Are there cases where it doesn't work
> and if so, why not (i.e. can we fix it) ?

You need 

  :match 'widget-child-match

in the definition of the 'child' widget, then it seems to work for the
cases I have tried.

Re: Creating recursive customization types / widgets

[Ted Zlatanov]

On 30 Nov 2003, monnier@iro.umontreal.ca wrote:

>> Below is a new widget named "child", which should simplify both
>> tasks a lot.
> 
> Neat.  I have no idea why it's called `child' and the resulting
> use of `child' in (define-widget 'foo 'child ...) does not look
> particularly intuitive, but I can't think of anything better either.

I like the patch, and I'm OK with "child" but here's some alternate
suggestions: recursive, inherited, derived, subtype, extending.

Ted

Re: Creating recursive customization types / widgets

[Thien-Thi Nguyen]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

   'recursive' and 'delayed' under development.

hehe, "fecund-root".

thi

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>
>> Neat.  I have no idea why it's called `child' and the resulting
>> use of `child' in (define-widget 'foo 'child ...) does not look
>> particularly intuitive, but I can't think of anything better either.
>
> Because it has a single child widget, and the new widget basically
> behave like the child, except for allowing recursion.

Actually, now I remember.  I though of it as a potential base class
for all widgets with a single child.  But it is not entirely
appropriate for that.

> I called it 'recursive' and 'delayed' under development.
>
> It is a common pattern in OOP.  Having an object that wraps another
> object, delegates message to the other object, and thus acts like a
> proxy.  So 'wrapper', delegator' or 'proxy' could be used as well.

My current favorite name would be 'proxy', but I do not feel strongly
about it.  What do you think?

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Ted Zlatanov <tzz@lifelogs.com> writes:

> I like the patch, and I'm OK with "child" but here's some alternate
> suggestions: recursive, inherited, derived, subtype, extending.

It is a bit weird to name a base class 'derived' or 'subtype' :-)
extending and inherited are a bit non-specific.  recursive is ok.

Re: Creating recursive customization types / widgets

[Juri Linkov]

Per Abrahamsen <abraham@dina.kvl.dk> writes:
> Per Abrahamsen <abraham@dina.kvl.dk> writes:
>> Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>>> Neat.  I have no idea why it's called `child' and the resulting
>>> use of `child' in (define-widget 'foo 'child ...) does not look
>>> particularly intuitive, but I can't think of anything better either.
>>
>> Because it has a single child widget, and the new widget basically
>> behave like the child, except for allowing recursion.
>
> Actually, now I remember.  I though of it as a potential base class
> for all widgets with a single child.  But it is not entirely
> appropriate for that.

The name "child" is not suitable in this case because it has
a sense only in a "parent-child" relationship between two entities.
So, let's consider some terminology to choose a better name:

Tree - recursive data structure
Node - item of a tree
Root - initial node of a tree
Leaf - terminal node of a tree
Cell - data object in Lisp data structure ("cons cell", "pair")

So depending on whether you perceive a new widget as a whole structure
(such as e.g. displayed by the `widget-browse-mode' in a widget
buffer) or only as one element of such structure, I suggest you
to name it either "tree" or "node".

>> I called it 'recursive' and 'delayed' under development.
>>
>> It is a common pattern in OOP.  Having an object that wraps another
>> object, delegates message to the other object, and thus acts like a
>> proxy.  So 'wrapper', delegator' or 'proxy' could be used as well.
>
> My current favorite name would be 'proxy', but I do not feel strongly
> about it.  What do you think?

These names are too implementation-specific, but from user's point of view
the name "node" is more clear.

BTW, adding new nodes to a tree in this new widget is easy,
but I can't find a way to delete a node.  Is it possible?

-- 
http://www.jurta.org/emacs/

Re: Creating recursive customization types / widgets

[Richard Stallman]

The doc string for `child' is now clear, but it shows
that `child' is not the right name for it.

ISTR that there is a frequently used term for an object
whose value will be computed only when you actually refer to it,
but it has been so many years that I don't remember the term.
Is it "lazy"?  Maybe this type should be called `lazy'.

`delayed' is ok too.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Juri Linkov <juri@jurta.org> writes:

> So depending on whether you perceive a new widget as a whole structure
> (such as e.g. displayed by the `widget-browse-mode' in a widget
> buffer) or only as one element of such structure, I suggest you
> to name it either "tree" or "node".

It is both.

I'd like to reserve `tree' for a customize-browse ui widget, and node
is rather non-descriptive.  Non-recursive datastructures can have
nodes as well.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Richard Stallman <rms@gnu.org> writes:

> ISTR that there is a frequently used term for an object
> whose value will be computed only when you actually refer to it,
> but it has been so many years that I don't remember the term.
> Is it "lazy"?  Maybe this type should be called `lazy'.

The word is lazy, as in lazy evaluation.

> `delayed' is ok too.

'lazy' and 'delayed' are good because they describe how the widget
accomplish its task.  But I now believe 'recursive' is best, because
it described what the task is.  Also 

  (define-widget 'binary-tree 'recursive ...)

reads well:  A binary tree is a recursive datastructure with the
following attributes ...

That lazy or delayed expansion is needed for recursive datastructures
is an (admittedly important) implementation detail.

May I commit the widget under the name `recursive'?

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Juri Linkov <juri@jurta.org> writes:

> BTW, adding new nodes to a tree in this new widget is easy,
> but I can't find a way to delete a node.  Is it possible?

I don't understand the question.  Are you speaking of the 'child'
widget, or the 'binary-tree-of-string' example?

If the later, then you can't delete or add a single node in binary
tree.  If you do, the tree is no longer binary.  Binary trees always
have an odd number of nodes.  You can add two nodes by converting a
leaf node to an interior node, and you can delete two subtrees by
converting an interior node to a leaf node.

Re: Creating recursive customization types / widgets

[David Kastrup]

Richard Stallman <rms@gnu.org> writes:

> The doc string for `child' is now clear, but it shows
> that `child' is not the right name for it.
> 
> ISTR that there is a frequently used term for an object
> whose value will be computed only when you actually refer to it,
> but it has been so many years that I don't remember the term.
> Is it "lazy"?  Maybe this type should be called `lazy'.
> 
> `delayed' is ok too.

dynamic?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

tapsellferrier.co.uk Host name lookup failure

[Robert J. Chassell]

Sorry to bother the rest of you -- but this is the best way I know to
tell Nic Ferrier <nferrier@tapsellferrier.co.uk> the problem:

Nic:  over the past week I have sent several messages to you off-list
and have got back bounces saying

     Xdefer: <nferrier@tapsellferrier.co.uk> reason: (ERR164) router 
     inet_hosts: DNS error: Host name lookup failure: Connection refused

Please do what you can.  Thank you.

-- 
    Robert J. Chassell                         Rattlesnake Enterprises
    http://www.rattlesnake.com                  GnuPG Key ID: 004B4AC8
    http://www.teak.cc                             bob@rattlesnake.com

Re: Creating recursive customization types / widgets

[David Kastrup]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Juri Linkov <juri@jurta.org> writes:
> 
> > So depending on whether you perceive a new widget as a whole structure
> > (such as e.g. displayed by the `widget-browse-mode' in a widget
> > buffer) or only as one element of such structure, I suggest you
> > to name it either "tree" or "node".
> 
> It is both.
> 
> I'd like to reserve `tree' for a customize-browse ui widget, and node
> is rather non-descriptive.  Non-recursive datastructures can have
> nodes as well.

There is nothing in the widget as far as I can see that requires it to
be used only for recursive data structures, even though that is its
primary purpose.  Its principal feature is that the type information
is evaluated delayed or dynamically.  It is conceivable, for example,
that the exact type depends on the value of a different variable, or
the availability of some feature at run-time.  One could use that
widget even in that case, and it would have nothing to do with
recursion.

So I think something like "lazy" or "dynamic" or "late" will be a
better name than "recursive".

Unless I am misunderstanding something here.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

David Kastrup <dak@gnu.org> writes:

> It is conceivable, for example, that the exact type depends on the
> value of a different variable, or the availability of some feature
> at run-time.  One could use that widget even in that case, and it
> would have nothing to do with recursion.

I don't know if that would work.  The :type value isn't evaluated like
a Lisp expression, it is expanded in widget specific ways.

Re: Creating recursive customization types / widgets

[Richard Stallman]

    'lazy' and 'delayed' are good because they describe how the widget
    accomplish its task.  But I now believe 'recursive' is best, because
    it described what the task is.  Also 

      (define-widget 'binary-tree 'recursive ...)

    reads well:  A binary tree is a recursive datastructure with the
    following attributes ...

That use is recursive, but the widget doesn't require you to use
recursion.  Its essence is lazy or delayed evaluation.  So I think
that should be the name.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Richard Stallman <rms@gnu.org> writes:

> That use is recursive, but the widget doesn't require you to use
> recursion.  Its essence is lazy or delayed evaluation.  So I think
> that should be the name.

Ok, I'll call it lazy.

Re: Creating recursive customization types / widgets

[Per Abrahamsen]

Here is documentation patch describing the use of the new widget.  Is
it ok to commit that, and the lazy widget code itself, to CVS?

2003-12-03  Per Abrahamsen  <abraham@dina.kvl.dk>

	* customize.texi (Defining New Types): Document use of the
        `lazy' widget. 

*** customize.texi.~1.36.~	2003-11-30 14:59:10.000000000 +0100
--- customize.texi	2003-12-03 16:18:56.000000000 +0100
***************
*** 1,6 ****
  @c -*-texinfo-*-
  @c This is part of the GNU Emacs Lisp Reference Manual.
! @c Copyright (C) 1997, 1998, 1999, 2000, 2002 Free Software Foundation, Inc.
  @c See the file elisp.texi for copying conditions.
  @setfilename ../info/customize
  @node Customization, Loading, Macros, Top
--- 1,6 ----
  @c -*-texinfo-*-
  @c This is part of the GNU Emacs Lisp Reference Manual.
! @c Copyright (C) 1997, 1998, 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
  @c See the file elisp.texi for copying conditions.
  @setfilename ../info/customize
  @node Customization, Loading, Macros, Top
***************
*** 373,378 ****
--- 373,379 ----
  * Composite Types::
  * Splicing into Lists::
  * Type Keywords::
+ * Defining New Types::
  @end menu
  
  All customization types are implemented as widgets; see @ref{Top, ,
***************
*** 1056,1061 ****
--- 1057,1123 ----
  @end ignore
  @end table
  
+ @node Defining New Types
+ @subsection Defining New Types
+ 
+ In the previous sections we have described how to construct elaborate
+ type specifications for @code{defcustom}.  In some cases you may want to
+ give such a type specification a name.  The obvious case is when you are
+ using the same type for many user options, rather than repeat the
+ specification for each option, you can give the type specification a
+ name once, and use that name each @code{defcustom}.  The other case is
+ when a user option accept a recursive datastructure.  To make it
+ possible for a datatype to refer to itself, it needs to have a name.
+ 
+ Since custom types are implemented as widgets, the way to define a new
+ customize type is to define a new widget.  We are not going to describe
+ the widget interface here in details, see @ref{Top, , Introduction,
+ widget, The Emacs Widget Library}, for that.  Instead we are going to
+ demonstrate the minimal functionality needed for defining new customize
+ types by a simple example.
+ 
+ @example
+ (define-widget 'binary-tree-of-string 'lazy
+   "A binary tree made of cons-cells and strings."
+   :offset 4
+   :tag "Node"
+   :type '(choice (string :tag "Leaf" :value "")
+                  (cons :tag "Interior"
+                        :value ("" . "") 
+                        binary-tree-of-string
+                        binary-tree-of-string)))
+ 
+ (defcustom foo-bar ""
+   "Sample variable holding a binary tree of strings."
+   :type 'binary-tree-of-string)
+ @end example
+ 
+ The function to define a new widget is name @code{define-widget}.  The
+ first argument is the symbol we want to make a new widget type.  The
+ second argument is a symbol representing an existing widget, the new
+ widget is going to be defined in terms of difference from the existing
+ widget.  For the purpose of defining new customization types, the
+ @code{lazy} widget is perfect, because it accept a @code{:type} keyword
+ argument with the same syntax as the keyword argument to
+ @code{defcustom} with the same name.  The third argument is a
+ documentation string for the new widget.  You will be able to see that
+ string with the @kbd{M-x widget-browse @key{ret} binary-tree-of-string
+ @key{ret}} command.  
+ 
+ After these mandatory arguments follows the keyword arguments.  The most
+ important is @code{:type}, which describes the datatype we want to match
+ with this widget.  Here a @code{binary-tree-of-string} is described as
+ being either a string, or a cons-cell whose car and cdr are themselves
+ both @code{binary-tree-of-string}.  Note the reference to the widget
+ type we are currently in the process of defining.  The @code{:tag}
+ attribute is a string to name the widget in the user interface, and the
+ @code{:offset} argument are there to ensure that child nodes are
+ indented four spaces relatively to the parent node, making the tree
+ structure apparent in the customization buffer.
+ 
+ The @code{defcustom} shows how the new widget can be used as an ordinary
+ customization type. 
+ 
  @ignore
     arch-tag: d1b8fad3-f48c-4ce4-a402-f73b5ef19bd2
  @end ignore

Re: Creating recursive customization types / widgets

[Kevin Rodgers]

Richard Stallman wrote:

>     'lazy' and 'delayed' are good because they describe how the widget
>     accomplish its task.  But I now believe 'recursive' is best, because
>     it described what the task is.  Also 
> 
>       (define-widget 'binary-tree 'recursive ...)
> 
>     reads well:  A binary tree is a recursive datastructure with the
>     following attributes ...
> 
> That use is recursive, but the widget doesn't require you to use
> recursion.  Its essence is lazy or delayed evaluation.  So I think
> that should be the name.
 
Can widgets have aliases, like variables and functions?


-- 
Kevin Rodgers