fix issue 9, add preliminary lists module

10 files changed, 373 insertions, 9 deletions

diff --git a/CHANGES b/CHANGES
index ad144113..c7289d3b 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,3 +1,12 @@
+20070217
+	repair /appl/lib/libc.b and /appl/lib/libc0.b strncmp implementations (used only by c2l output) [inferno-os issue 9]
+20070216
+	add /module/lists.m, /appl/lib/lists.b, and lists(2)
+20070209
+	remove debugging -d option to exportfs call in emu/Plan9/devsrv9.c(!)
+20070206
+	/appl/svc/auth.sh: replace exit by raise
+	/man/2/styxservers: document replychan and replydirect
 20070201
 	update US timezone files to save energy
 20070131
diff --git a/appl/lib/libc.b b/appl/lib/libc.b
index 0acc6f42..8260277e 100644
--- a/appl/lib/libc.b
+++ b/appl/lib/libc.b
@@ -113,9 +113,16 @@ strncmp(s1: string, s2: string, n: int): int
 {
 	l1 := len s1;
 	l2 := len s2;
-	for(i := 0; i < l1 && i < l2 && i < n; i++)
+	m := n;
+	if(m > l1)
+		m = l1;
+	if(m > l2)
+		m = l2;
+	for(i := 0; i < m; i++)
 		if(s1[i] != s2[i])
-			return s1[i]-int s2[i];
+			return s1[i]-s2[i];
+	if(i == n)
+		return 0;
 	return l1-l2;
 }
 
diff --git a/appl/lib/libc0.b b/appl/lib/libc0.b
index a9a2e834..aa6caff2 100644
--- a/appl/lib/libc0.b
+++ b/appl/lib/libc0.b
@@ -170,12 +170,20 @@ strcmp(s1: array of byte, s2: array of byte): int
 
 strncmp(s1: array of byte, s2: array of byte, n: int): int
 {
-	l1 := strlen(s1);
-	l2 := strlen(s2);
-	for(i := 0; i < l1 && i < l2 && i < n; i++)
-		if(s1[i] != s2[i])
-			return int s1[i]-int s2[i];
-	return l1-l2;
+	i1 := i2 := 0;
+	while(n > 0){
+		c1 := int s1[i1++];
+		c2 := int s2[i2++];
+		n--;
+		if(c1 != c2){
+			if(c1 > c2)
+				return 1;
+			return -1;
+		}
+		if(c1 == 0)
+			break;
+	}
+	return 0;
 }
 
 strchr(s: array of byte, n: int): array of byte
diff --git a/appl/lib/lists.b b/appl/lib/lists.b
new file mode 100644
index 00000000..e12a2e5d
--- /dev/null
+++ b/appl/lib/lists.b
@@ -0,0 +1,131 @@
+implement Lists;
+
+include "lists.m";
+
+# these will be more useful when p is a closure
+allsat[T](p: ref fn(x: T): int, l: list of T): int
+{
+	for(; l != nil; l = tl l)
+		if(!p(hd l))
+			return 0;
+	return 1;
+}
+
+anysat[T](p: ref fn(x: T): int, l: list of T): int
+{
+	for(; l != nil; l = tl l)
+		if(p(hd l))
+			return 1;
+	return 0;
+}
+
+map[T](f: ref fn(x: T): T, l: list of T): list of T
+{
+	if(l == nil)
+		return nil;
+	return f(hd l) :: map(f, tl l);
+}
+
+filter[T](p: ref fn(x: T): int, l: list of T): list of T
+{
+	if(l == nil)
+		return nil;
+	if(p(hd l))
+		return hd l :: filter(p, tl l);
+	return filter(p, tl l);
+}
+
+partition[T](p: ref fn(x: T): int, l: list of T): (list of T, list of T)
+{
+	l1: list of T;
+	l2: list of T;
+	for(; l != nil; l = tl l)
+		if(p(hd l))
+			l1 = hd l :: l1;
+		else
+			l2 = hd l :: l2;
+	return (reverse(l1), reverse(l2));
+}
+
+append[T](l: list of T, x: T): list of T
+{
+	# could use the reversing loops instead if this is ever a bottleneck
+	if(l == nil)
+		return x :: nil;
+	return hd l :: append(tl l, x);
+}
+
+concat[T](l: list of T, l2: list of T): list of T
+{
+	if(l2 == nil)
+		return l;
+	for(l = reverse(l); l2 != nil; l2 = tl l2)
+		l = hd l2 :: l;
+	return reverse(l);
+}
+
+combine[T](l: list of T, l2: list of T): list of T
+{
+	for(; l != nil; l = tl l)
+		l2 = hd l :: l2;
+	return l2;
+}
+
+reverse[T](l: list of T): list of T
+{
+	rl: list of T;
+	for(; l != nil; l = tl l)
+		rl = hd l :: rl;
+	return rl;
+}
+
+last[T](l: list of T): T
+{
+	# l must not be nil
+	while(tl l != nil)
+		l = tl l;
+	return hd l;
+}
+
+# delete the first instance of x in l
+delete[T](x: T, l: list of T): list of T
+	for { T =>	eq:	fn(a, b: T): int; }
+{
+	o: list of T;
+	for(; l != nil; l = tl l)
+		if(T.eq(x, hd l)){
+			l = tl l;
+			for(; o != nil; o = tl o)
+				l = hd o :: l;
+			break;
+		}
+	return l;
+}
+
+pair[T1, T2](l1: list of T1, l2: list of T2): list of (T1, T2)
+{
+	if(l1 == nil && l2 == nil)
+		return nil;
+	return (hd l1, hd l2) :: pair(tl l1, tl l2);
+}
+
+unpair[T1, T2](l: list of (T1, T2)): (list of T1, list of T2)
+{
+	l1: list of T1;
+	l2: list of T2;
+	for(; l != nil; l = tl l){
+		(v1, v2) := hd l;
+		l1 = v1 :: l1;
+		l2 = v2 :: l2;
+	}
+	return (reverse(l1), reverse(l2));
+}
+
+ismember[T](x: T, l: list of T): int
+	for { T =>	eq:	fn(a, b: T): int; }
+{
+	for(; l != nil; l = tl l)
+		if(T.eq(x, hd l))
+			return 1;
+	return 0;
+}
diff --git a/dis/lib/libc.dis b/dis/lib/libc.dis
index 9102cafc..48abdb58 100644
--- a/dis/lib/libc.dis
+++ b/dis/lib/libc.dis
diff --git a/dis/lib/libc0.dis b/dis/lib/libc0.dis
index f68e7be3..acafb5be 100644
--- a/dis/lib/libc0.dis
+++ b/dis/lib/libc0.dis
diff --git a/dis/lib/lists.dis b/dis/lib/lists.dis
new file mode 100644
index 00000000..0c3a8243
--- /dev/null
+++ b/dis/lib/lists.dis
diff --git a/include/version.h b/include/version.h
index 8763c132..ea9166bd 100644
--- a/include/version.h
+++ b/include/version.h
@@ -1 +1 @@
-#define VERSION	"Fourth Edition (20070213)"
+#define VERSION	"Fourth Edition (20070217)"
diff --git a/man/2/lists b/man/2/lists
new file mode 100644
index 00000000..730bcb45
--- /dev/null
+++ b/man/2/lists
@@ -0,0 +1,185 @@
+.TH LISTS 2
+.SH NAME
+lists: allsat, anysat, append, combine, concat, delete, filter, ismember, last, map, pair, partition, rev, unpair\- list operations
+.SH SYNOPSIS
+.EX
+include "lists.m"
+lists := load Lists Lists->PATH;
+
+append:    fn[T](l: list of T, x: T): list of T;
+combine:   fn[T](l1: list of T, l2: list of T): list of T;
+concat:    fn[T](l1: list of T, l2: list of T): list of T;
+delete:    fn[T](x: T, l: list of T): list of T
+             for { T => eq:  fn(a, b: T): int; };
+ismember:  fn[T](x: T, l: list of T): int
+             for { T =>  eq: fn(a, b: T): int; };
+last:      fn[T](l: list of T): T;
+pair:      fn[T1, T2](l1: list of T1, l2: list of T2):
+             list of (T1, T2);
+reverse:   fn[T](l: list of T): list of T;
+unpair:    fn[T1, T2](l: list of (T1, T2)):
+             (list of T1, list of T2);
+
+allsat:    fn[T](p: ref fn(x: T): int, l: list of T): int;
+anysat:    fn[T](p: ref fn(x: T): int, l: list of T): int;
+filter:    fn[T](p: ref fn(x: T): int, l: list of T): list of T;
+map:       fn[T](f: ref fn(x: T): T, l: list of T): list of T;
+partition: fn[T](p: ref fn(x: T): int, l: list of T):
+             (list of T, list of T);
+.EE
+.SH DESCRIPTION
+The module provides operations on lists of type
+.IR T ,
+which may be any reference type, or
+.BR string .
+Reference types are
+.BR array ,
+.BR chan ,
+.BR list ,
+.BR module ,
+and
+.BI ref "adt".
+None of the operations change their parameter lists: they always return a new list.
+.PP
+First, there is a group of common list operations.
+.PP
+.B Append
+returns a new list with the elements of
+.I l
+followed by the element
+.IR x .
+.PP
+.B Combine
+returns a new list that has the elements of both
+.I l1
+and
+.I l2
+in no defined order.
+.PP
+.B Concat
+returns a new list that has the elements of
+.I l1
+followed by the elements of
+.IR l2 .
+.PP
+.B Delete
+returns a new list in which the first element of
+.I l
+that is equal to
+.I x
+has been removed (all others remain).
+.I X
+must be an adt reference type
+.I T
+with an operation
+.IB T .eq
+that returns true (non-zero) if two values of type
+.I T
+are considered equal.
+.PP
+.B Ismember
+returns 1 if
+there is an element of
+.I l
+that is equal to
+.IR x .
+.PP
+.B Last
+returns the value of the element at the end of list
+.IR l .
+A run-time error occurs if
+.I l
+is nil.
+.PP
+.B Pair
+takes two lists
+.I l1
+and
+.IR l2 ,
+and returns a new list of tuples
+.BI ( v1,\ v2 )
+in which each element of
+.I l1
+has been paired with the corresponding element of
+.IR l2 .
+A run-time error occurs if the lists are not equal in length.
+.PP
+.B Reverse
+returns a new list containing the elements of
+.I l
+in reverse order.
+.PP
+.B Unpair
+takes a list of tuples
+.BI ( v1,\ v2 )
+and returns a tuple of lists
+.BI ( l1,\ l2 )
+where
+.I l1
+contains the first element of each tuple, and
+.I l2
+contains the second element of each tuple.
+.PP
+A second group of operations applies a function
+.I f
+or a Boolean predicate
+.I p
+to each element of a list
+.IR l ,
+returning a transformed list or a Boolean value.
+A predicate
+.I p
+must return non-zero if its parameter value satisfies its condition, and must return zero if it does not.
+.PP
+.B Allsat
+returns 1 if all elements of
+.I l
+satisfy
+.IR p ,
+and returns 0 otherwise.
+.PP
+.B Anyset
+returns 1 if any element of
+.I l
+satisfies
+.IR p ,
+and returns 0 otherwise.
+.PP
+.B Filter
+returns a new list containing only the elements of
+.I l
+that satisfy
+.IR p .
+.PP
+.B Map
+returns a new list in which each element of
+.I l
+has been transformed by
+.I f
+(ie, if
+.I l
+is
+.IB e0 :: e1 ::  ...
+then the result is
+.IB f(e0) :: f(e1) :: ... ).
+.PP
+.B Partition
+returns a tuple of lists
+.BI ( l1,\ l2 )
+of lists where
+.I l1
+contains all elements of
+.I l
+that satisfy
+.I p
+and
+.I l2
+contains all elements of
+.I l
+that do not satisfy
+.IR p .
+.SH SOURCE
+.B /appl/lib/lists.b
+.SH BUGS
+The current implementation of polymorphism is limited to reference types and strings,
+which in turn limits use of this module.
diff --git a/module/lists.m b/module/lists.m
new file mode 100644
index 00000000..242c9bf6
--- /dev/null
+++ b/module/lists.m
@@ -0,0 +1,24 @@
+Lists: module
+{
+	map:	fn[T](f: ref fn(x: T): T, l: list of T): list of T;
+	allsat:	fn[T](p: ref fn(x: T): int, l: list of T): int;
+	anysat:	fn[T](p: ref fn(x: T): int, l: list of T): int;
+	filter:	fn[T](p: ref fn(x: T): int, l: list of T): list of T;
+	partition:	fn[T](p: ref fn(x: T): int, l: list of T): (list of T, list of T);
+
+	append:	fn[T](l: list of T, x: T): list of T;
+	concat:	fn[T](l: list of T, l2: list of T): list of T;
+	combine:	fn[T](l: list of T, l2: list of T): list of T;
+	reverse:	fn[T](l: list of T): list of T;
+	last:	fn[T](l: list of T): T;
+	delete:	fn[T](x: T, l: list of T): list of T
+		for { T => eq:	fn(a, b: T): int; };
+	pair:	fn[T1, T2](l1: list of T1, l2: list of T2): list of (T1, T2);
+	unpair:	fn[T1, T2](l: list of (T1, T2)): (list of T1, list of T2);
+	ismember:	fn[T](x: T, l: list of T): int
+		for { T =>	eq:	fn(a, b: T): int; };
+};
+
+#sort?
+#join
+#split