From db7b65f8c76cc6734f984d181945d4965742c4da Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sun, 2 Sep 2012 03:31:01 -0700 Subject: * eval.c (eval_init): Follow function renames. * hash.c (make_hash): Likewise. * lib.c (assq): Renamed to assql for consistency. (aconsq_new): Renamed to aconsql_new. (aconsq_new_l): Renamed to aconsql_new_l. (alist_remove_test): Use equal rather than eq. Association lists use equal equality by default. (alist_nremove): Use memqual rather than memq. (alist_nremove1): Use equal rather than eq. (merge): Bugfix: unnecessary consing caused by using append instead of nconc on list pieces that are already destructively chopped up. This has implications for the efficiency of sort over lists! (multi_sort_less): Implement key functions. (multi_sort): Interface change: arguments rearranged, and new argument to specify key functions. * lib.h (assoc, assq, assql, aconsq_new, aconsq_new_l): Declarations renamed. (multi_sort): Declaration updated. * txr.1: Documented alist library, list sorting and completed documenting lazy library. * txr.vim: multi-sort highlighted. --- ChangeLog | 30 +++++++ eval.c | 6 +- hash.c | 4 +- lib.c | 37 +++++---- lib.h | 8 +- txr.1 | 267 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- txr.vim | 2 +- 7 files changed, 318 insertions(+), 36 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1692c8d0..a549dba9 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,33 @@ +2012-09-02 Kaz Kylheku + + * eval.c (eval_init): Follow function renames. + + * hash.c (make_hash): Likewise. + + * lib.c (assq): Renamed to assql for consistency. + (aconsq_new): Renamed to aconsql_new. + (aconsq_new_l): Renamed to aconsql_new_l. + (alist_remove_test): Use equal rather than eq. Association lists + use equal equality by default. + (alist_nremove): Use memqual rather than memq. + (alist_nremove1): Use equal rather than eq. + (merge): Bugfix: unnecessary consing caused by using append + instead of nconc on list pieces that are already destructively + chopped up. This has implications for the efficiency of sort + over lists! + (multi_sort_less): Implement key functions. + (multi_sort): Interface change: arguments rearranged, and new + argument to specify key functions. + + * lib.h (assoc, assq, assql, aconsq_new, aconsq_new_l): Declarations + renamed. + (multi_sort): Declaration updated. + + * txr.1: Documented alist library, list sorting and completed + documenting lazy library. + + * txr.vim: multi-sort highlighted. + 2012-09-01 Kaz Kylheku * txr.1: Lots of new documentation. Major rearrangement of document, diff --git a/eval.c b/eval.c index 60e0cebf..5ef0f34e 100644 --- a/eval.c +++ b/eval.c @@ -2372,10 +2372,10 @@ void eval_init(void) reg_fun(intern(lit("cat-vec"), user_package), func_n1(cat_vec)); reg_fun(intern(lit("assoc"), user_package), func_n2(assoc)); - reg_fun(intern(lit("assq"), user_package), func_n2(assq)); + reg_fun(intern(lit("assql"), user_package), func_n2(assql)); reg_fun(intern(lit("acons"), user_package), func_n3(acons)); reg_fun(intern(lit("acons-new"), user_package), func_n3(acons_new)); - reg_fun(intern(lit("aconsq-new"), user_package), func_n3(aconsq_new)); + reg_fun(intern(lit("aconsql-new"), user_package), func_n3(aconsql_new)); reg_fun(intern(lit("alist-remove"), user_package), func_n1v(alist_remove)); reg_fun(intern(lit("alist-nremove"), user_package), func_n1v(alist_nremove)); reg_fun(intern(lit("copy-cons"), user_package), func_n1(copy_cons)); @@ -2383,7 +2383,7 @@ void eval_init(void) reg_fun(intern(lit("merge"), user_package), func_n4o(merge, 2)); reg_fun(intern(lit("sort"), user_package), func_n3o(sort, 2)); reg_fun(intern(lit("find"), user_package), func_n4o(find, 2)); - reg_fun(intern(lit("multi-sort"), user_package), func_n2(multi_sort)); + reg_fun(intern(lit("multi-sort"), user_package), func_n3o(multi_sort, 2)); reg_fun(intern(lit("find-if"), user_package), func_n3o(find_if, 2)); reg_fun(intern(lit("set-diff"), user_package), func_n4o(set_diff, 2)); diff --git a/hash.c b/hash.c index 03967967..68f5929c 100644 --- a/hash.c +++ b/hash.c @@ -364,8 +364,8 @@ val make_hash(val weak_keys, val weak_vals, val equal_based) h->userdata = nil; h->hash_fun = equal_based ? equal_hash : eql_hash; - h->assoc_fun = equal_based ? assoc : assq; - h->acons_new_l_fun = equal_based ? acons_new_l : aconsq_new_l; + h->assoc_fun = equal_based ? assoc : assql; + h->acons_new_l_fun = equal_based ? acons_new_l : aconsql_new_l; return hash; } diff --git a/lib.c b/lib.c index 8fa575e1..74e64a90 100644 --- a/lib.c +++ b/lib.c @@ -3710,7 +3710,7 @@ val assoc(val key, val list) return nil; } -val assq(val key, val list) +val assql(val key, val list) { while (list) { val elem = car(list); @@ -3756,9 +3756,9 @@ val *acons_new_l(val key, val *new_p, val *list) } } -val aconsq_new(val key, val value, val list) +val aconsql_new(val key, val value, val list) { - val existing = assq(key, list); + val existing = assql(key, list); if (existing) { set(*cdr_l(existing), value); @@ -3768,9 +3768,9 @@ val aconsq_new(val key, val value, val list) } } -val *aconsq_new_l(val key, val *new_p, val *list) +val *aconsql_new_l(val key, val *new_p, val *list) { - val existing = assq(key, *list); + val existing = assql(key, *list); if (existing) { if (new_p) @@ -3788,7 +3788,7 @@ val *aconsq_new_l(val key, val *new_p, val *list) static val alist_remove_test(val item, val key) { - return eq(car(item), key); + return equal(car(item), key); } val alist_remove(val list, val keys) @@ -3806,7 +3806,7 @@ val alist_nremove(val list, val keys) val *plist = &list; while (*plist) { - if (memq(car(car(*plist)), keys)) + if (memqual(car(car(*plist)), keys)) *plist = cdr(*plist); else plist = cdr_l(*plist); @@ -3820,7 +3820,7 @@ val alist_nremove1(val list, val key) val *plist = &list; while (*plist) { - if (eq(car(car(*plist)), key)) + if (equal(car(car(*plist)), key)) *plist = cdr(*plist); else plist = cdr_l(*plist); @@ -3880,20 +3880,20 @@ val merge(val list1, val list2, val lessfun, val keyfun) if (funcall2(lessfun, el1, el2)) { val next = cdr(list1); *cdr_l(list1) = nil; - list_collect_append(ptail, list1); + list_collect_nconc(ptail, list1); list1 = next; } else { val next = cdr(list2); *cdr_l(list2) = nil; - list_collect_append(ptail, list2); + list_collect_nconc(ptail, list2); list2 = next; } } if (list1) - list_collect_append(ptail, list1); + list_collect_nconc(ptail, list1); else - list_collect_append(ptail, list2); + list_collect_nconc(ptail, list2); return out; } @@ -3994,14 +3994,16 @@ val sort(val seq, val lessfun, val keyfun) return seq; } -static val multi_sort_less(val funcs, val llist, val rlist) +static val multi_sort_less(val funcs_cons, val llist, val rlist) { + cons_bind (funcs, key_funcs, funcs_cons); val less = t; while (funcs) { val func = pop(&funcs); - val left = pop(&llist); - val right = pop(&rlist); + val test = pop(&key_funcs); + val left = if3(test, funcall1(test, pop(&llist)), pop(&llist)); + val right = if3(test, funcall1(test, pop(&rlist)), pop(&rlist)); if (funcall2(func, left, right)) break; @@ -4015,14 +4017,15 @@ static val multi_sort_less(val funcs, val llist, val rlist) return less; } -val multi_sort(val funcs, val lists) +val multi_sort(val lists, val funcs, val key_funcs) { val tuples = mapcarv(func_n0v(identity), lists); if (functionp(funcs)) funcs = cons(funcs, nil); - tuples = sort_list(tuples, func_f2(funcs, multi_sort_less), identity_f); + tuples = sort_list(tuples, func_f2(cons(funcs, key_funcs), + multi_sort_less), identity_f); return mapcarv(func_n0v(identity), tuples); } diff --git a/lib.h b/lib.h index 475dfe7b..eedaa1cb 100644 --- a/lib.h +++ b/lib.h @@ -618,12 +618,12 @@ mem_t *cobj_handle(val cobj, val cls_sym); val cptr(mem_t *ptr); mem_t *cptr_get(val cptr); val assoc(val key, val list); -val assq(val key, val list); +val assql(val key, val list); val acons(val car, val cdr, val list); val acons_new(val key, val value, val list); val *acons_new_l(val key, val *new_p, val *list); -val aconsq_new(val key, val value, val list); -val *aconsq_new_l(val key, val *new_p, val *list); +val aconsql_new(val key, val value, val list); +val *aconsql_new_l(val key, val *new_p, val *list); val alist_remove(val list, val keys); val alist_remove1(val list, val key); val alist_nremove(val list, val keys); @@ -635,7 +635,7 @@ val mapcon(val fun, val list); val mappend(val fun, val list); val merge(val list1, val list2, val lessfun, val keyfun); val sort(val seq, val lessfun, val keyfun); -val multi_sort(val funcs, val lists); +val multi_sort(val lists, val funcs, val key_funcs); val find(val list, val key, val testfun, val keyfun); val find_if(val pred, val list, val key); val set_diff(val list1, val list2, val testfun, val keyfun); diff --git a/txr.1 b/txr.1 index 6644d612..8bbe4e16 100644 --- a/txr.1 +++ b/txr.1 @@ -6559,8 +6559,60 @@ which returns non-nil. .SS Functions find and find-if +.TP +Syntax: + + (find [ []]) + (find-if []) + +.TP +Description: + +The find and find-if functions search through a list for an item which +matches a key, or satisfies a predicate function, respectively. + +The keyfun argument specifies a function which is applied to the elements +of the list to produce the comparison key. If this argument is omitted, +then the untransformed elements of the list themselves are searched. + +The find function's testfun argument specifies the test function which +is used to compare the comparison keys from the list to the search key. +If this argument is omitted, then the equal function is used. +The first element from the list whose comparison key (as retrieved by +the key function) matches the search (under the test function) +is returned. If no such element is found, nil is returned. + +The find-if function's predfun argument specifies a predicate function +which is applied to the successive comparison keys pulled from the list +by applying the key function to successive elements. The first element +for which the predicate function yields true is returned. If no such +element is found, nil is returned. + .SS Function set-diff +.TP +Syntax: + (set_diff [ []]) + +.TP +Description: + +The set-diff function treats two lists as if they were sets and computes +the set difference: a list which contains those elements in list1 which +do not occur in list2. + +Element equivalence is determined by a combination of testfun and keyfun. +Elements are compared pairwise, and each element of a pair is passed through +the keyfun function to produce a comparison value. The comparison values +are compared with the testfun function. If keyfun is omitted, then the +untransformed elements themselves are compared, and if testfun is omitted, +then the equal function is used. + +If list1 contains duplicate elements which do not occur in list2 (and +thus are preserved in the set difference) then these duplicates appear +in the resulting list. Furthermore, the order of the items from list1 is +preserved. + .SS Functions mapcar, mappend, mapcar* and mappend* .TP @@ -6764,28 +6816,187 @@ Examples: .SH ASSOCIATION LISTS +Association lists are ordinary lists formed according to a special convention. +Firstly, any empty list is a valid association list. A non-empty association +list contains only cons cells as the key elements. These cons cells are +understood to represent key/value associations, hence the name "association +list". + .SS Function assoc +.TP +Syntax: + + (assoc ) + +.TP +Description: + +The assoc function searches an association list for a cons cell whose +car field contains the given key (with equality determined by the equal +function). The first such cons is returned. If no such cons is found, +nil is returned. + .SS Function assq +.TP +Syntax: + + (assql ) + +.TP +Description: + +The assql function is just like assoc, except that the equality test +is determined using the eql function rather than equal. + .SS Function acons +.TP +Syntax: + + (acons ) + +.TP +Description: + +The acons function constructs a new alist by consing a new cons to the +front of an existing alist. The following equivalence holds: + + (acons car cdr alist) <--> (cons (cons car cdr) alist) + .SS Function acons-new -.SS Function aconsq-new +.TP +Syntax: + + (acons-new ) + +.TP +Description: + +The acons-new function searches alist, as if using the assoc function, +for an existing cell which matches the key provided by the car argument. +If such a cell exists, then its cdr field is overwritten with the cdr +argument, and then the list is returned. If no such cell exists, then +a new list is returned by adding a new cell to the input list consisting +of the car and cdr values, as if by the acons function. + +.SS Function aconsql-new + +.TP +Syntax: + + (aconsql-new ) + +.TP +Description: + +This function is like acons-new, except that the eql function is used +for equality testing. Thus, the list is searched for an existing cell +as if using the assql function rather than assoc. .SS Function alist-remove +.TP +Syntax: + + (alist-remove ) + +.TP +Description: + +The alist-remove function takes an input alist and produces a duplicate +from which cells matching the specified keys have been removed. The keys +argument is a list of the keys not to appear in the output list. + .SS Function alist-nremove +.TP +Syntax: + + (alist-nremove ) + +.TP +Description: + +The alist-nremove function is like alist-remove, but potentially destructive. +The input list may be destroyed and its structural material re-used to form the +output list. The application should not retain references to the input list. + .SS Function copy-alist +.TP +Syntax: + + (copy-alist ) + +.TP +Description: + +The copy-alist function duplicates an alist. Unlike copy-list, which +only duplicates list structure, copy-alist also duplicates each cons +cell of the input alist. That is to say, each element of the output list +is produced as if by the copy-cons function applied to the corresponding +element of the input list. + .SH LIST SORTING .SS Function merge +.TP +Syntax: + + (merge ) + +.TP +Description: + +The merge function merges two sorted lists into a single sorted +list. The semantics and defaulting behavior of the lessfun and keyfun arguments +are the same as those of the sort function. The input lists are assumed to be +sorted according to these functions. + +This function is destructive. The application should not retain references to +the input lists, since the output list is formed out of the structure of the +input lists. + .SS Function multi-sort +.TP +Syntax: + + (multi-sort []) + +.TP +Description: + +The multi-sort function regards a list of lists to be the columns of a +database. The corresponding elements from each list constitute a record. +These records are to be sorted, producing a new list of lists. + +The columns argument supplies the list of lists which comprise the columns of +the database. The lists should ideally be of the same length. If the lists are +of different lengths, then the shortest list is taken to be the length of the +database. Excess elements in the longer lists are ignored, and do not appear in +the sorted output. + +The less-funcs argument supplies a list of comparison functions which are +applied to the columns. Successive functions correspond to successive +columns. If less-funcs is an empty list, then the sorted database will +emerge in the original order. If less-funcs contains exactly one function, then +the rows of the database is sorted according to the first column. The remaining +columns simply follow their row. If less-funcs contains more than one +function, then additional columns are taken into consideration if the items +in the previous columns compare equal. For instance if two elements from column +one compare equal, then the corresponding second column elements are compared +using the second column comparison function. + +The optional key-funcs argument supplies transformation functions through which +column entries are converted to comparison keys, similarly to the single key +function used in the sort function and others. If there are more key functions +than less functions, the excess key functions are ignored. + .SH LAZY LISTS AND LAZY EVALUATION .SS Function make-lazy-cons @@ -6862,6 +7073,29 @@ another lazy cons (as in the example under make-lazy-cons). .SS Function generate +.TP Syntax: + (generate ) + +.TP Description: + +The generate function produces a lazy list which dynamically produces items +according to the following logic. + +The arguments to generate are functions which do not take any arguments. The +return value of generate is a lazy list. + +When the lazy list is accessed, for instance with the functions car and cdr, it +produces items on demand. Prior to producing each item, the while-fun is +called. If it returns a true boolean value (any value other than nil), then +the gen-fun function is called, and its return value is incorporated as +the next item of the lazy list. But if while-fun yields nil, then the lazy +list immediately terminates. + +Prior to returning the lazy list, generate invokes the while-fun one time. +If while-fun yields nil, then generate returns the empty list nil instead +of a lazy list. Otherwise, it instantiates a lazy list, and invokes +the gen-func to populate it with the first item. + .SS Function repeat .SS Operator gen @@ -6875,20 +7109,19 @@ Syntax: Description: The gen operator produces a lazy list, in a manner similar to the generate -function. Whereas the generate function (documented later in this manual) -takes functional arguments, the gen operator takes two expressions, which is -often more convenient. +function. Whereas the generate function takes functional arguments, the gen +operator takes two expressions, which is often more convenient. The return value of gen is a lazy list. When the lazy list is accessed, for instance with the functions car and cdr, it produces items on demand. Prior to producing each item, the is evaluated, in its original -lexical scope. If the expression yields true, then -is evaluated, and its return value is incorporated as the next item of the lazy -list. If the expression yields false, then the lazy list immediately -terminates. +lexical scope. If the expression yields a true value (non-nil), then + is evaluated, and its return value is incorporated as +the next item of the lazy list. If the expression yields nil, then the lazy +list immediately terminates. The gen operator itself immediately evaluates before -producing the lazy list. If the expression yields false, then the operator +producing the lazy list. If the expression yields nil, then the operator returns the empty list nil. Otherwise, it instantiates the lazy list and invokes the to force the first item. @@ -6958,6 +7191,22 @@ Example: .SS Function force +.TP +Syntax: + + (force ) + +.TP +Description: + +The force function accepts a promise object produced by the delay function. +The first time force is invoked on a promise object, the promise expression +is evaluated (in its original lexical environment, regardless of where +in the program the force call takes place). The value of the expression is +cached inside the promise and returned, becoming the return value of the +force function call. If the force function is invoked additional times on +the same promise, the cached value is retrieved. + .SH CHARACTERS AND STRINGS .SS Function mkstring diff --git a/txr.vim b/txr.vim index c53730b2..746f51be 100644 --- a/txr.vim +++ b/txr.vim @@ -83,7 +83,7 @@ syn keyword txl_keyword contained list-vector copy-vec sub-vec cat-vec syn keyword txl_keyword contained replace-vec assoc assq acons acons-new syn keyword txl_keyword contained aconsq-new alist-remove alist-nremove copy-cons syn keyword txl_keyword contained copy-alist merge sort find set-diff length -syn keyword txl_keyword contained sub ref replace refset +syn keyword txl_keyword contained sub ref replace refset multi-sort syn keyword txl_keyword contained symbol-function func-get-form func-get-env syn keyword txl_keyword contained functionp interp-fun-p *random-state* -- cgit v1.2.3