diff options
| -rw-r--r-- | ChangeLog | 30 | ||||
| -rw-r--r-- | eval.c | 6 | ||||
| -rw-r--r-- | hash.c | 4 | ||||
| -rw-r--r-- | lib.c | 37 | ||||
| -rw-r--r-- | lib.h | 8 | ||||
| -rw-r--r-- | txr.1 | 267 | ||||
| -rw-r--r-- | txr.vim | 2 |
7 files changed, 318 insertions, 36 deletions
@@ -1,3 +1,33 @@ +2012-09-02 Kaz Kylheku <kaz@kylheku.com> + + * 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 <kaz@kylheku.com> * txr.1: Lots of new documentation. Major rearrangement of document, @@ -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)); @@ -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; } @@ -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); } @@ -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); @@ -6559,8 +6559,60 @@ which returns non-nil. .SS Functions find and find-if +.TP +Syntax: + + (find <key> <list> [<testfun> [<keyfun>]]) + (find-if <predfun> <list> [<keyfun>]) + +.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 <list1> <list2> [<testfun> [<keyfun>]]) + +.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 <key> <alist>) + +.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 <key> <alist>) + +.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 <car> <cdr> <alist>) + +.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 <car> <cdr> <alist>) + +.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 <car> <cdr> <alist>) + +.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 <alist> <keys>) + +.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 <alist> <keys>) + +.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 <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 <list1> <list2> <lessfun> <keyfun>) + +.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 <columns> <less-funcs> [<key-funcs>]) + +.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 <while-fun> <gen-fun>) + +.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 <while-expression> is evaluated, in its original -lexical scope. If the expression yields true, then <produce-item-expression> -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 +<produce-item-expression> 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 <while-expression> 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 <produce-item-expression> to force the first item. @@ -6958,6 +7191,22 @@ Example: .SS Function force +.TP +Syntax: + + (force <promise>) + +.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 @@ -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* |