Re: Spec reorganisation
On Thu, 19 Feb 2009, Carl Mäsak wrote:
Timothy (), Moritz ():
Speaking of Tree, let me quote from IRC:
09:23 masak it's a bit unfortunate that the identifier 'Tree' is now
squatted by an internal class in Perl 6, which is not
general
enough to reprenest an arbitrary tree data structure.
I fully agree with that. If it's not the most general tree, don't name
it Tree.
Hmm. I'm wanting the API for this tree structure to be able to
represent arbitrary general trees. I'm limited by the fact that the main
trees I'm familiar with are filesystems and XML, and a little with LDAP.
Can you give examples of types of tree that aren't representable with what
I'm doing?
I'll give it a shot. As previously seen in S16:
role Tree does Tree::Node {
has Tree::Node $root; # The root directory
has Tree::Node $cwn; # The current working directory (node)
has Bool $can_multiple_parent; # Nodes can have multiple parents
has Bool $can_link; # Unix links, Windows shortcuts, etc
}
A tree is a graph without cycles.
Ok, maybe I should call this Graph then, but that would *really*
confuse people.
The concept of a root is very common in computer representations, but in
no way necessary for a general tree. In fact, in phylogenetics, it's
business as usual to handle unrooted trees. This makes the $root attribute
meaningless in at least some cases.
Interesting. I'm happy to assume that $root is allowed to be
Undefined, I think. But let me ask a question; were you to represent an
unrooted tree in a computer, how would you do it so that, if you had to look
around the tree, you could do it? You'd need some node that was an
entry-point into the tree. That's the purpose I'm trying to get at here.
Also, I have a suspicion that the problem we have here is that the
term node is being used slightly differently by the computer science
community and the phylogenetic community. When I look at the unrooted tree
on:
http://en.wikipedia.org/wiki/Phylogenetic_tree
...it looks to me like they don't call anything a node unless it has a
dot at it. But if I were building a data structure to represent that tree
(eg. so that I could auto-generate the image on the Wikipedia page), I'd make
a root node for it, but somehow label it an invisible node, and when the
image was generated, while there would be a node for it inside the computer,
there'd be no dot on the graph. So in Computer Science terms, there'd be a
root node, but in Phylogenetic terms, there wouldn't. And I think I'd do
things that way whether I was using Perl6 or not.
(incidentally, my knowledge of phylogenetics is entirely drawn from
that Wikipedia page).
Of course, I could be wrong, so I encourage you to keep prodding :).
The $cwn is meaningless in most tree implementations I can think of.
Agreed, as in XML. But assuming that that can be Undefined is also
not a problem.
As to $can_multiple_parent, a structure which allows nodes with
multiple parents is not a tree, it's a directed graph.
Right, in mathematical/computer science terms, but how often to you
hear people refer to a file tree/filesystem tree vs. file graph :).
Hmm. I've also seen it called Plex. Would it make everyone happier
if I called the whole thing Plex instead? Admittedly I've never heard
anyone refer to a filesystem plex, but at least that has no semantic
conflicts, and is short enough that it could catch on :).
Whether symlinks are allowed is (1) fairly filesystem-specific, and (2) not
very pertinent to the tree object itself.
Hmm. I agree. I think what we have here is a miscommunication
(probably my fault :) ) about what I'm trying to achieve.
What I want to do is make an API which has many features that the IETF
community would call MAY instead of MUST; ie. You don't have to do X, but
if you do, call it Y. I agree it's filesystem-specific; it should probably
be a private attribute or something. I was wanting the info stored somewhere
so that it could be looked up, but maybe the thing to do is to let people try
to link, and catch exceptions :).
What's left is, in effect, this:
role Tree does Tree::Node {
}
While an empty role _does_ indeed have potential, and could be made to
work with most tree implementations out there, it's also a bit of a
shame to pretend to provide four attributes with Tree, neither of
which is actually an attribute of a general graph-theoretical tree.
Just sayin'.
Depends on what you're trying to achieve; see above :).
Another thing I found myself saying yesterday was that designing a
language also involves knowing when not to decide things for the
programmer. I wish there was a way to say this, while also
emphasizing my appreciation for the many good changes to S16. Files
and I/O are obviously areas where the bikeshedding tendency grows
extra strong, so I'm glad someone actually goes in and does things to
the spec.
But I
Re: Spec reorganisation
Em Qui, 2009-02-19 às 22:57 +1100, Timothy S. Nelson escreveu:
Interesting. I'm happy to assume that $root is allowed to be
Undefined, I think. But let me ask a question; were you to represent an
unrooted tree in a computer, how would you do it so that, if you had to look
around the tree, you could do it? You'd need some node that was an
entry-point into the tree. That's the purpose I'm trying to get at here.
Not at all, that is the same as saying that a list must always be
ordered, and that it should have a beggining. Circular Lists are very
well known.
If you think in a BTree, for instance, you usually don't have a root
node, since a BTree is simply a way to view a list, and you might
receive a node and work only from that context onward. That even applies
for filesystems: what if your process calls (2)chroot? what happens to
the root node?
On the other hand, I have to disagree with masak that it would be an
empty role, because there is indeed one operation that you can always do
in a tree node:
role Tree::Node {
method List lookup(*%options);
}
on a BTree you would have
$node.lookup(:left);
$node.lookup(:right);
on a Filesystem you would have
$node.lookup(:namefoo.txt);
$node.lookup(:name..);
$node.lookup(:parent);
$node.lookup(:root);
$node.lokoup(:absolute/tmp/foo.txt);
on a match object
$node.lookup(:hiearchy/named/token/with/subtokens);
on a XML document you would have
$node.lookup(:xpathsomexpathexpression);
$node.lookup(:attributefoo);
# of course, DOM would be a complementary API.
Where it could be spec that
$node.lookup()
should return all the child elements as a lazy list, which means that a
generic tree traversal could be written (and maybe the tree transforming
sub-language).
daniel
Re: Spec reorganisation
On Thu, 2009-02-19 at 22:57 +1100, Timothy S. Nelson wrote: On Thu, 19 Feb 2009, Carl Mäsak wrote: A tree is a graph without cycles. That's insufficient. In fact, there are a number of ways that the general concept of an acyclic graph must be constrained before you get something you can call a 'tree'. The concept of a root is very common in computer representations, but in no way necessary for a general tree. In fact, in phylogenetics, it's business as usual to handle unrooted trees. This makes the $root attribute meaningless in at least some cases. Interesting. I'm happy to assume that $root is allowed to be Undefined, I think. But let me ask a question; were you to represent an unrooted tree in a computer, how would you do it so that, if you had to look around the tree, you could do it? You'd need some node that was an entry-point into the tree. That's the purpose I'm trying to get at here. A tree with nodes but without a root is not a tree -- it's a collection of trees, more commonly called a grove or forest. -'f
Re: Spec reorganisation
On Thu, 19 Feb 2009, Daniel Ruoso wrote:
Em Qui, 2009-02-19 às 22:57 +1100, Timothy S. Nelson escreveu:
Interesting. I'm happy to assume that $root is allowed to be
Undefined, I think. But let me ask a question; were you to represent an
unrooted tree in a computer, how would you do it so that, if you had to look
around the tree, you could do it? You'd need some node that was an
entry-point into the tree. That's the purpose I'm trying to get at here.
Not at all, that is the same as saying that a list must always be
ordered, and that it should have a beggining. Circular Lists are very
well known.
I guess I'm trying to say something slightly different. Let me give
an example. If you tried to create a circular list in Perl, with, eg.
class Node {
has $nextnode;
has $data;
}
...and you got a few, and linked them in a circle, but then got rid of
all variables that refer to them, then if I understand correctly, you'd be
entirely unable to get the data out again. But given one (or more) variables
that points to this list, you'd be able to walk around in it and retrieve all
the data.
What I want the Tree role to do is to be a place where we can ensure
that at least one of the nodes is referred to.
If you think in a BTree, for instance, you usually don't have a root
node, since a BTree is simply a way to view a list, and you might
receive a node and work only from that context onward. That even applies
for filesystems: what if your process calls (2)chroot? what happens to
the root node?
It changes :). So I guess chroot should be replaced with a setter on
$Tree.root :).
On the other hand, I have to disagree with masak that it would be an
empty role, because there is indeed one operation that you can always do
in a tree node:
role Tree::Node {
method List lookup(*%options);
}
[snipped lookup examples]
Hmm. It seems we're trying to achieve the same things, but you want
everything done as parameters to a lookup method, whereas I want everything
done as attributes and methods on the node.
:)
-
| Name: Tim Nelson | Because the Creator is,|
| E-mail: wayl...@wayland.id.au| I am |
-
BEGIN GEEK CODE BLOCK
Version 3.12
GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V-
PE(+) Y+++ PGP-+++ R(+) !tv b++ DI D G+ e++ h! y-
-END GEEK CODE BLOCK-
Re: Spec reorganisation
Hi, Timothy S. Nelson wrote: I'm not suggesting here that we specify the interfaces to all the modules listed in the Camel book, or anything like that. Instead, I'm suggesting that the S32 space be used for documenting the objects that we don't seem to be able to get away from. Aye. Synopsis - Api documentation is a good transition. - The IO, Tree, and DateTime stuff being drafted in S16 Speaking of Tree, let me quote from IRC: 09:23 masak it's a bit unfortunate that the identifier 'Tree' is now squatted by an internal class in Perl 6, which is not general enough to reprenest an arbitrary tree data structure. I fully agree with that. If it's not the most general tree, don't name it Tree. After looking through the Phlanx project (which lists 100 or so top perl modules), and the list in the Camel book, I can only see one or two other things we might eventually need, and these can be worried about later. Anyway, my suggestion is that a folder called S32-standard-modules be created in the Spec directory, I'd just call that 'lib/', in good old Perl tradition. and that within this folder, the following files be created from the specified sources: - Tree.pod -- S16 - DateTime.pod -- S16 (needs lots of work) - IO.pod -- S16 - Most of the stuff from the S29 Function Packages, in separate files This would leave S29 free to be solely a list of the functions that do not need to have a package specified when called, and can in most cases simply specify what standard library functions they call. It would also leave S16-IO free to deal with things that are not specific to the object(s). like time(), bare say/print being a compile time error etc. I really like the idea, but I'd go one step further: In addition to the API documentation you could also just implement the thing. Especially the DateTime stuff doesn't need any fancy feature that rakudo doesn't do yet (afaict), so it would be nice not only to spec it, but also to provide a pure Perl 6 implementation that can later be shared among compilers. Perl 6 is full of stuff that's specced but not implemented, and I'd like to see that gap closed as much as possible. Cheers, Moritz -- Moritz Lenz http://perlgeek.de/ | http://perl-6.de/ | http://sudokugarden.de/
Re: Spec reorganisation
Sorry, this was supposed to go to the mailing list. On Wed, 18 Feb 2009, Timothy S. Nelson wrote: After looking through the Phlanx project (which lists 100 or so top perl modules), and the list in the Camel book, I can only see one or two other things we might eventually need, and these can be worried about later. Anyway, my suggestion is that a folder called S32-standard-modules be created in the Spec directory, I'd just call that 'lib/', in good old Perl tradition. Hmm. But isn't lib/ for actual code? As a follow-up to my own message, I'm now suggesting (after some IRC discussion) that it maybe should be called S32-setting-library. Perl 6 is full of stuff that's specced but not implemented, and I'd like to see that gap closed as much as possible. Agreed. My main problem is that I don't know any Parrot :). But as long as things can be written in Perl6, I'm happy to work at them. ...and as a follow-up to this, I ran into someone on IRC who *does* want to do this if it requires Parrot, as something to help them learn PIR. :) - | Name: Tim Nelson | Because the Creator is,| | E-mail: wayl...@wayland.id.au| I am | - BEGIN GEEK CODE BLOCK Version 3.12 GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V- PE(+) Y+++ PGP-+++ R(+) !tv b++ DI D G+ e++ h! y- -END GEEK CODE BLOCK- - | Name: Tim Nelson | Because the Creator is,| | E-mail: wayl...@wayland.id.au| I am | - BEGIN GEEK CODE BLOCK Version 3.12 GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V- PE(+) Y+++ PGP-+++ R(+) !tv b++ DI D G+ e++ h! y- -END GEEK CODE BLOCK-
Re: Spec reorganisation
Timothy (), Moritz ():
Speaking of Tree, let me quote from IRC:
09:23 masak it's a bit unfortunate that the identifier 'Tree' is now
squatted by an internal class in Perl 6, which is not
general
enough to reprenest an arbitrary tree data structure.
I fully agree with that. If it's not the most general tree, don't name
it Tree.
Hmm. I'm wanting the API for this tree structure to be able to
represent arbitrary general trees. I'm limited by the fact that the main
trees I'm familiar with are filesystems and XML, and a little with LDAP.
Can you give examples of types of tree that aren't representable with what
I'm doing?
I'll give it a shot. As previously seen in S16:
role Tree does Tree::Node {
has Tree::Node $root; # The root directory
has Tree::Node $cwn; # The current working directory (node)
has Bool $can_multiple_parent; # Nodes can have multiple parents
has Bool $can_link; # Unix links, Windows shortcuts, etc
}
A tree is a graph without cycles. The concept of a root is very
common in computer representations, but in no way necessary for a
general tree. In fact, in phylogenetics, it's business as usual to
handle unrooted trees. This makes the $root attribute meaningless in
at least some cases.
The $cwn is meaningless in most tree implementations I can think of.
As to $can_multiple_parent, a structure which allows nodes with
multiple parents is not a tree, it's a directed graph. Whether
symlinks are allowed is (1) fairly filesystem-specific, and (2) not
very pertinent to the tree object itself.
What's left is, in effect, this:
role Tree does Tree::Node {
}
While an empty role _does_ indeed have potential, and could be made to
work with most tree implementations out there, it's also a bit of a
shame to pretend to provide four attributes with Tree, neither of
which is actually an attribute of a general graph-theoretical tree.
Just sayin'.
Another thing I found myself saying yesterday was that designing a
language also involves knowing when not to decide things for the
programmer. I wish there was a way to say this, while also
emphasizing my appreciation for the many good changes to S16. Files
and I/O are obviously areas where the bikeshedding tendency grows
extra strong, so I'm glad someone actually goes in and does things to
the spec.
But I do believe that creating a general tree role of the above kind
would be unfortunate in at least two ways: it'd limit the possible
implementations of trees (while not giving much back in terms of an
advantage), and it'd use up the perfectly good name Tree. I'd say
keep it simple, keep directory structures and XML DOM trees separate,
and don't let Perl second-guess what you want to implement.
// Carl
