From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Rivka Miller Newsgroups: gmane.emacs.help Subject: Re: `list-of' macro snippet [regarding Comprehensions] Date: Sun, 28 Oct 2012 17:49:05 -0700 (PDT) Message-ID: References: <44777946-db62-48fa-9e99-2fd06c6d296c@g18g2000vbf.googlegroups.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1351471816 8342 80.91.229.3 (29 Oct 2012 00:50:16 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 29 Oct 2012 00:50:16 +0000 (UTC) Cc: Rivka Miller To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Mon Oct 29 01:50:24 2012 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TSdYd-0003yq-Iu for geh-help-gnu-emacs@m.gmane.org; Mon, 29 Oct 2012 01:50:23 +0100 Original-Received: from localhost ([::1]:51192 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TSdYV-0003J6-9P for geh-help-gnu-emacs@m.gmane.org; Sun, 28 Oct 2012 20:50:15 -0400 Original-Received: by 10.224.105.205 with SMTP id u13mr7606878qao.6.1351471745960; Sun, 28 Oct 2012 17:49:05 -0700 (PDT) Original-Received: by 10.52.28.45 with SMTP id y13mt18270430vdg.10.1351471745925; Sun, 28 Oct 2012 17:49:05 -0700 (PDT) Original-Path: usenet.stanford.edu!e17no4737440qar.0!news-out.google.com!gf5ni61qab.0!nntp.google.com!e17no4737438qar.0!postnews.google.com!w2g2000vbc.googlegroups.com!not-for-mail Original-Newsgroups: gnu.emacs.sources,gnu.emacs.help,comp.emacs Complaints-To: groups-abuse@google.com Injection-Info: w2g2000vbc.googlegroups.com; posting-host=108.193.255.245; posting-account=V5Tx-QoAAACNTDxOswIwdOklJAUE-vym Original-NNTP-Posting-Host: 108.193.255.245 User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (Windows NT 5.1; rv:12.0) Gecko/20100101 Firefox/12.0,gzip(gfe) Injection-Date: Mon, 29 Oct 2012 00:49:05 +0000 Original-Xref: usenet.stanford.edu gnu.emacs.sources:13597 gnu.emacs.help:195148 comp.emacs:102672 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:87477 Archived-At: To help focus on the issue I dont know if they are necessary for the context of the operation of the comprehensions macro that I cant get to work in elisp. The original is below but the indentation does not match the original, nor the paren matching in the last two defuns. I tried helping myself by various google and groups searches but if there was any satisfactory reply, it missed my results. (defmacro comp ((e &rest qs) 12) (if (null qs) '(cons ,e ,12) ; rule A (let ((q1 (car qs)) (q (cdr qs))) (if (not(eq (cadr q1) '<-)) ; a generator? '(if ,ql (comp (,e ,@q),12) ,12) ; rule B (let ((v (car ql)) ; rule C (l1 (third q)) (h (gentemp "H-")) (us (gentemp "US-")) (usl (gentemp "US1-"))) '(labels ((,h (,us) ; corresponds to a letrec (if (null ,us) ,12 (let ((,v (car ,us)) (,usl (cdr ,us))) (comp (,e ,@q) (,h ,us1)))))) (,h ,l1))))))) (defun open-bracket (stream ch) (do ((l nil) (c (read stream t nil t)(read stream t nil t))) ((eq c '|]|) '(comp ,(reverse l) ())) (push c l)) ) (defun closing-bracket (stream ch) '|]|) (eval-when (compile load eval) (set-macro-character #\[ #'open-bracket) (set-macro-character #\] #'closing-bracket)) R On Oct 28, 5:19=A0pm, Rivka Miller wrote: > Discusuion continued from the link > > http://groups.google.com/group/gnu.emacs.sources/browse_thread/thread... > > For those of you who might be interested in this topic. I am including > the html source of the two links as well as verbatim text discussion > to continue the topic. > > \begin{verbatim}http://web.archive.org/web/20021108231431/http://www.cs.n= wu.edu/acade... > Lisp Exercises > > Some of these exercises are in addition to or in place of those in > Graham or Wilensky. > > SOME (Chapter 8, Ex. 7) > > Define (has-number-p s-exp) to return true if the s-expression is or > contains a number. > > > (has-number-p 1) > T > > (has-number-p 'a) > NIL > > (has-number-p '(1 (b (2 c) ((3))))) > > T > > Implement this using a simple conditional, recursion, and SOME. > Letting SOME do some of the work is more efficient than a pure CAR-CDR > recursive solution. > > Wilensky, Ex. 13.2 revised > > Define the macro our-if to have the form > > (OUR-IF test > =A0 :THEN exp1 exp2 ... > =A0 :ELSE exp3 exp4 ...) > > This does about the same thing as: > > (COND (test exp exp ...) > =A0 =A0 =A0 (T else-exp else-exp ...)) > > Almost everything is optional in our-if except the test. Here are some > legal forms and their results: > > > (our-if (> 3 1) :then 'ok) > OK > > (our-if (< 5 3) :else 'ok) > OK > > (our-if (> 3 1) :else 'oops) > NIL > > (our-if (> 3 1) :then) > NIL > > (our-if (> 3 1) :else 'oops :then 'ok) > > OK > > Closures (Chapter 12) > > Define (make-balance initial-balance) to return a function that takes > 0 or 1 arguments. If that function is called with 0 arguments, it > returns the current balance. If called with 1 argument, which should > be a number, it adds that number to the current balance, and returns > the new balance. > > > (setq bal (make-balance 100)) > > > (funcall bal 10) > 110 > > (funcall bal -50) > 60 > > (funcall bal) > > 60 > > Modifying list pointers (Chapter 15) > > Define (delete-car list) to modify and return list with the first > element of list deleted. > > > (setq l '(a b c)) > (A B C) > > (delete-car l) > (B C) > > L > > (B C) > > Note: it's impossible to destructively delete the only item in a list > and turn it into NIL, but delete-car should at least return NIL in > that case. > > MAPCAN (Chapter 15) > > Define (collect-numbers s-exp) to return a list of all the numbers in > the s-expression s-exp. s-exp may be an atom, a list, or a list of s- > expressions. > > > (collect-numbers 1) > (1) > > (collect-numbers 'a) > NIL > > (collect-numbers '(1 (b (2 c) ((3))))) > > (1 2 3) > > Implement this using a simple conditional, recursion, and MAPCAN. > Letting MAPCAN do some of the work is more efficient than a pure CAR- > CDR recursive solution. Don't worry about duplicate numbers in the > result. > > Wilensky, Ex. 15.7 revised > > Adding elements to the end of a list is usually inefficient in Lisp: > > =A0 =A0 (append list (list item)) is the worst possible approach, because > list gets copied every time a new item is added. If you use this form > to build a list N long, you'll have done N squared cons's. Imagine > doing that for a simple 100-element list! > =A0 =A0 (nconc list (list item)) doesn't cons, but still gets very slow a= s > the list gets long, because Lisp has to cdr all the way to the end of > the list in order to find the last cons cell to modify. > > A classic solution is to create a data structure called a tconc > structure (for "tail concatenate"), which holds two pointers to the > same list: > > =A0 =A0 a head pointer to the whole list, and > =A0 =A0 a tail pointer to the last cons cell of that list. > > With this data structure, you can add new elements to the end of the > list with just a few quick operations, no matter how long the list is, > and you can still get the whole list whenever you need it. > > Therefore, your job is to: > > =A0 =A0 Define (make-tconc [ list ]) to return a tconc structure pointing > to list. If no list is given, a tconc structure for an empty list > should be returned. > =A0 =A0 Define (tconc tconc-structure [item item ...]) to add the items, > if any, to the end of the list pointed to by tconc-structure, update > tconc-strcture appropriately, and return the new value of the internal > list. > =A0 =A0 Define (tconc-list tconc-structure list ) to add the items in lis= t > to the end of the internal list. > > Note that you can get the internal list at any time with (tconc tconc- > structure). > > > (setq tc (make-tconc)) > > > (tconc tc 1) > (1) > > (tconc tc 2 3) > (1 2 3) > > (tconc tc) > > (1 2 3) > > Each successive call to tconc should be efficient, no matter how long > the internal list has grown. One test of your tconc structure is that > it always obeys the following rule: > > =A0 =A0 (eq (last head-pointer) tail-pointer) > > Queues (Chapter 15) > > A queue is a standard data structure in computer science, that's very > useful whenever you want to take data in the order in which it occurs. > > For example, keystrokes and mouse clicks in an interface need to be > handled in the order in which they occur. If they happen too fast for > the program to keep up, the program should save the unprocessed clicks > in a queue until it can get to them. > > Once you've done the tconc exercise, defining queue functions is easy: > > =A0 =A0 Define (make-queue [list]) to create a queue data structure, > initialized to the elements of list. > =A0 =A0 Define (enqueue item queue) to add the item to the end of the > queue. > =A0 =A0 Define (dequeue queue) to remove the first item from the queue an= d > return it. If the queue is empty, nil is returned. > > list-of (an advanced macro) > > [ Inspired by Guy Lapalme's article in Lisp Pointers, Apr-Jun 91 ] > > list-of is macro that simplifies collecting lists of values of > expressions. Though this description is long, and the macro is > powerful, it's actually quite simple and can be implemented in less > than half a page of code. > > The general syntax is > > =A0 =A0 (LIST-OF exp generator-or-filter generator-or-filter ...) > > It's easiest to explain by starting with simple examples. > > =A0 =A0 > (list-of (1+ x) (x :in '(1 2 3))) > =A0 =A0 (2 3 4) > > exp is (1+ x) and (x :in '(1 2 3)) is a generator. A generator is > anything that has the form (variable :in list). This generator > generates three values for x, namely 1, 2, and 3. list-of returns a > list of the value of (1+ x) for those three values of x. > > =A0 =A0 > (list-of (1+ x) (x :in '(1 2 3)) (oddp x)) > =A0 =A0 (2 4) > > The exp is simply the variable x, the generator is as before, and > (oddp x) is a filter. A filter is any expression that doesn't look > like a generator. The filter says "keep only those values of x that > are odd." Hence, list-of only collects values for x equal to 1 and 3. > > That's it. Any number of generators and filters can be given. They are > applied from left to right. If there are two generators, the second > repeats itself for every value created by the first, e.g., > > =A0 =A0 > (setq l '(a b)) > =A0 =A0 (A B) > =A0 =A0 > (list-of (list x y) (x :in l) (y :in )) > =A0 =A0 ((A A) (A B) (B A) (B B)) > > Likewise, the filters apply in order. > > =A0 =A0 > (setq l '(1 2 3 4)) > =A0 =A0 (1 2 3 4) > =A0 =A0 > (list-of (list x y) (x :in l) (oddp x) (y :in l) (evenp y)) > =A0 =A0 ((1 2) (1 4) (3 2) (3 4)) > > This collects (list x y) for every x in l that is odd and every y in l > that is even. Notice that > > =A0 =A0 > (list-of (list x y) (x :in l) (y :in l) (oddp x) (evenp y)) > =A0 =A0 ((1 2) (1 4) (3 2) (3 4)) > > returns the same answer, but does more work. Trace oddp to see the > difference. > > One special case that follows naturally: > > =A0 =A0 (list-of exp) simply returns a list of exp. > > Our final examples are primarily for hard-core computer science types. > You can skip them if you wish. Neither are particularly efficient, but > they show the power of list-of. > > To define a function that gets all the permutations of a list: > > =A0 =A0 (defun perms (l) > =A0 =A0 =A0 (if (endp l) > =A0 =A0 =A0 =A0 =A0 (list '()) > =A0 =A0 =A0 =A0 =A0 (list-of (cons a p) > =A0 =A0 =A0 =A0 =A0 =A0 =A0(a :in l) > =A0 =A0 =A0 =A0 =A0 =A0 =A0(p :in (perms (remove a l :count 1)))))) > > The list-of collects "(cons a p) for every a in l and every p in the > permutations of l with a removed." > > To define a form of quicksort function: > > =A0 =A0 (defun qsort (l) > =A0 =A0 =A0 (if (endp l) > =A0 =A0 =A0 =A0 =A0 '() > =A0 =A0 =A0 =A0 =A0 (let ((a (car l)) (x (cdr l))) > =A0 =A0 =A0 =A0 =A0 =A0 (append (qsort (list-of (y :in x) (< y a))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (list a) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (qsort (list-of (y :in x) (>=3D y= a))))))) > > This splits l into those elements that are less than the car of l, and > those that are greater, sorts each sublist recursively, and joins the > results > \end{verbatim} > > \begin{verbatim}http://web.archive.org/web/20010911002454/http://www.cs.n= wu.edu/acade... > Macro Exercises > > defrule - a simple rule definer > > Define the macro defrule. The calling format is > > (defrule name > =A0 test test test ... > =A0 =3D> action action action) > > where test's and action's are expressions. This defines a rule called > name. > > Define the function run-rule to take a rule name and "run" it. Running > a rule is the same as evaluating > > (when (and test test test ...) > =A0 action action action ...) > > Example: > > (defrule watch-for-vacuum > =A0 (=3D *air-supply* 0) > =A0 =3D> (format t "Hold your breath!")) > > > (setq *air-supply* 0) > > (run-rule 'hate-vacuum) > > Hold your breath! > NIL > > There should be no eval's anywhere in your code. Hint: see the > discussion of thunks on page 46 of AI Programming. > with-output-to-list > > Common Lisp has a nice special form for building strings, called with- > ouput-to-string. The with-output-to-list macro adds similar > functionality to list building. It's calling format is > > (with-output-to-list (fn-name [variable]) > =A0expression expression ...) > > This evaluates the expressions with fn-name bound temporarily to a > function that takes zero or more arguments, efficiently adds them to > the end of the list in variable, and returns the current value of the > list. The value of the last expression is returned. Hint: read about > the built-in special form flet. > > As with with-output-to-string, if variable is omitted, fn-name adds > its arguments to a new empty list, and with-output-to-list returns the > final value of that list, rather than the value of the last > expression. Here are two examples: > > > (with-output-to-list (collect) > > =A0 =A0 (dolist (x '(1 2 3 4)) > =A0 =A0 =A0 (when (oddp x) (collect x)))) > (1 3) > > > (setq *l* '(a b)) > > (with-output-to-list (collect *l*) > > =A0 =A0 (dolist (x '(1 2 3 4)) > =A0 =A0 =A0 (when (oddp x) (collect x)))) > nil > > > *l* > > (a b 1 3) > > To be efficient, with-output-to-list should expand into code that uses > the tconc approach to list building (Wilensky, Common LispCraft, Chap > 15, Exercise 7, and the file list.exs in the c25/exercises area). You > should expect to generate fairly different expansions for the > "variable given" and "variable omitted" cases. > list-of - a simple iterator > > list-of has the following general calling format: > > (list-of expression form form ...) > > where form is either a generator or a filter. A generator is a list of > the form (variable :in expression). A filter is any expression that is > not a generator. Generators generate values, and filters accept > certain values (by returning true). There can be any number of > generators and filters in any order. > > list-of makes a list of all the values of expression created by the > generators and accepted by the filters. > > list-of is best explained with a series of examples: > > (list-of x) > =A0 =A0 returns a list of the value of x. There are no generators or > filters. > (list-of x (x :in l) (oddp x)) > =A0 =A0 returns "a list of those x's, where x is in l and x is odd." > (list-of (* x x) (x :in l)) > =A0 =A0 returns "a list of the square's of x, where x is in l." > (list-of (* x y) (x :in l) (y :in l)) > =A0 =A0 returns "a list of the products of x and y, where x and y are in > l." For example, if l =3D (2 3), this would multiply 2 x 2, 2 x 3, 3 x > 2, and 3 x 3, and return (4 6 6 9). > (list-of (* x y) (x :in l) (oddp x) (y :in l)) > =A0 =A0 returns "a list of the products of x and y, where x and y are in = l > and x is odd." For example, if l =3D (2 3), this would multiply 3 x 2, > and 3 x 3, and return (6 9). > > This may seem complicated, but in fact list-of can be defined in half > a dozen lines, or so. The first expression is put inside a call to > list, each filter expands into (when filter ...), each generator > expands into (mapcan #'(lambda (var) ...) list), and everything nests > recursively. The expansions of the above examples are, respectively: > > (list x) > > (mapcan #'(lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0(when (oddp x) > =A0 =A0 =A0 =A0 =A0 =A0 (list x))) > =A0 =A0 =A0 =A0 l) > > (mapcan #'(lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0(list (* x x))) > =A0 =A0 =A0 =A0 l) > > (mapcan #'(lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0(mapcan #'(lambda (y) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (list (* x y))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0l)) > =A0 =A0 =A0 =A0 l) > > (mapcan #'(lambda (x) > =A0 =A0 =A0 =A0 =A0 =A0(when (oddp x) > =A0 =A0 =A0 =A0 =A0 =A0 (mapcan #'(lambda (y) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(list (* x y))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 l))) > =A0 =A0 =A0 =A0 l) > > Hint: the best way to handle recursive macros is to define a recursive > "expander" function, i.e., > > (defmacro list-of (exp &rest forms) > =A0 (expand-list-of exp forms)) > > expand-list-of is just a normal function that returns the expansion of > a list-of call. The nice thing about it is that it can call itself > recursively, something that can be messy to do with macros. > \end{verbatim} > > I dont know if they are necessary for the context of the operation of > the comprehensions macro that I cant get to work in elisp. > > The original is below but the indentation does not match the original, > nor the paren matching in the last two defuns. I tried helping myself > by various google and groups searches but if there was any > satisfactory reply, it missed my results. > > (defmacro comp ((e &rest qs) 12) > =A0 (if (null qs) '(cons ,e ,12) =A0 =A0 =A0 =A0 =A0; rule A > =A0 =A0 (let ((q1 (car qs)) > =A0 =A0 =A0 =A0 =A0 (q (cdr qs))) > =A0 =A0 =A0 (if (not(eq (cadr q1) '<-)) =A0 =A0; a generator? > =A0 =A0 =A0 =A0 =A0 '(if ,ql (comp (,e ,@q),12) ,12) ; rule B > =A0 =A0 =A0 =A0 (let ((v (car ql)) =A0 =A0 =A0 =A0 =A0 =A0 =A0; rule C > =A0 =A0 =A0 =A0 =A0 =A0 =A0 (l1 (third q)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 (h (gentemp "H-")) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 (us (gentemp "US-")) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 (usl (gentemp "US1-"))) > =A0 =A0 =A0 =A0 =A0 '(labels ((,h (,us) =A0 =A0 =A0 =A0 =A0 ; corresponds= to a letrec > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (if (null ,us) ,12 > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (let ((,v (car ,us)) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (,usl (cd= r ,us))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (comp (,e ,@q) (,= h ,us1)))))) > =A0 =A0 =A0 =A0 =A0 =A0 =A0(,h ,l1))))))) > > (defun open-bracket (stream ch) > =A0 (do ((l nil) > =A0 =A0 =A0 =A0(c (read stream t nil t)(read stream t nil t))) > =A0 =A0 =A0 ((eq c '|]|) '(comp ,(reverse l) ())) > =A0 (push c l)) > ) > > (defun closing-bracket (stream ch) '|]|) > > (eval-when (compile load eval) > =A0 (set-macro-character #\[ #'open-bracket) > =A0 (set-macro-character #\] #'closing-bracket)) > > R