Hello everyone,
I am working on my first CL program (I am not a computer science
major - this is not homework), and I am close to being finished. It's
purpose is to create a linear structure that is self-similar at
several ratios. For example, if you choose for a structure to be self
similar at ratios 5:3:1 it will be exactly the same if you read it or
hear it every 1 unit, every 3 units, and every 5 units. Each ratio
contains a complete copy of the whole structure (though you have to
loop through the structure however many times to see its entire length
at a given ratio). So any number of ratios and any length of
structure can be build automatically and return a list with the
structure in (A B C D D C B A A) form. This is to be used for
assistance in planning music that I compose, or for images, writings,
etc.
The one problem that I am running into is a problem with setf.
Because any number of ratios may be input, I am automatically creating
variables and assigning names to them. I am doing it like this...
(setf (car (symbol-bundle 2 (list 'listx *counta*))) whatever)
*counta* is incremented with incf every time the recursive funtion
calls itself, and that works well.
This part...
(car (symbol-bundle 2 (list 'listx *counta*)))
...always returns the appropriate variable name listx1 listx2 listx3
etc.
However when I go to manually check to see if this is working, I see
that setf really isn't doing what it is supposed to here. For
example...
(setf listx1 '(1 2 3 4 5))
listx1 ------> (1 2 3 4 5)
Now say I go to change listx1 like this...
(setf (car (symbol-bundle 2 (list 'listx *counta*))) '(6 7 8 9 10))
----> (6 7 8 9 10)
listx1 ------> (1 2 3 4 5)
So even though this - (car (symbol-bundle 2 (list 'listx *counta*))) -
returns listsx1, and setf doesn't return any errors, when I check to
see if listx1 was changed, it wasn't.
If anybody has any ideas why setf is working this way, I would very
much appreciate it. It would be a big relief to me to finish this
"program" and use it in a multitude of ways, and I would be happy to
make the code available, as simple as it is.
Also - are there simple ways of automatically creating incremented
variable names? I tried intern on strings but that didn't work too
well, and settled on my current method.
Thank you,
Eric Belcastro
From: Maciej Katafiasz
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <fj9tcv$fi8$4@news.net.uni-c.dk>
Den Thu, 06 Dec 2007 14:01:39 -0800 skrev Eric:
> If anybody has any ideas why setf is working this way, I would very much
> appreciate it. It would be a big relief to me to finish this "program"
> and use it in a multitude of ways, and I would be happy to make the code
> available, as simple as it is.
SETF is a macro, and operates on places, not variables. This means that
attempts to use it on things that can't be usefully interpreted at macro
expansion time won't do what you want. In particular, operations on
dynamically supplied symbols won't work as you expect.
Because you know you're operating on symbols here, you can use SET, which
is a real function and will do what you mean. Or
(setf (symbol-value (...))), which is equivalent.
Cheers,
Maciej
In article
<····································@w28g2000hsf.googlegroups.com>,
Eric <·············@gmail.com> wrote:
> Hello everyone,
> I am working on my first CL program (I am not a computer science
> major - this is not homework), and I am close to being finished. It's
> purpose is to create a linear structure that is self-similar at
> several ratios. For example, if you choose for a structure to be self
> similar at ratios 5:3:1 it will be exactly the same if you read it or
> hear it every 1 unit, every 3 units, and every 5 units. Each ratio
> contains a complete copy of the whole structure (though you have to
> loop through the structure however many times to see its entire length
> at a given ratio). So any number of ratios and any length of
> structure can be build automatically and return a list with the
> structure in (A B C D D C B A A) form. This is to be used for
> assistance in planning music that I compose, or for images, writings,
> etc.
>
> The one problem that I am running into is a problem with setf.
> Because any number of ratios may be input, I am automatically creating
> variables and assigning names to them. I am doing it like this...
>
> (setf (car (symbol-bundle 2 (list 'listx *counta*))) whatever)
>
> *counta* is incremented with incf every time the recursive funtion
> calls itself, and that works well.
>
> This part...
>
> (car (symbol-bundle 2 (list 'listx *counta*)))
>
> ...always returns the appropriate variable name listx1 listx2 listx3
> etc.
>
> However when I go to manually check to see if this is working, I see
> that setf really isn't doing what it is supposed to here. For
> example...
>
> (setf listx1 '(1 2 3 4 5))
> listx1 ------> (1 2 3 4 5)
>
> Now say I go to change listx1 like this...
>
> (setf (car (symbol-bundle 2 (list 'listx *counta*))) '(6 7 8 9 10))
> ----> (6 7 8 9 10)
> listx1 ------> (1 2 3 4 5)
Well, SETF is a macro. There is some machinery at macroexpand time
that determines what SETF actually expands into.
? (macroexpand '(setf *foo* bar))
(SETQ *FOO* BAR)
? (macroexpand '(setf (aref *foo* 3) bar))
(CCL::ASET *FOO* 3 BAR)
? (macroexpand '(setf (car *foo*) bar))
(CCL::SET-CAR *FOO* BAR)
So you see that the place form gets analyzed at macroexpand time
(not runtime !!!) and the right code gets generated.
The wrong picture is:
(car (symbol-bundle 2 (list 'listx *counta*))) will return some
symbol and SETF will then do a SETQ on the symbol.
Above is wrong, since that would be at runtime. But SETF
determines at macroexpand time (for example when the
compiler macroexpands the code) what to use.
So, if you have a GLOBAL variables (which you should ALWAYS
write as *VARIABLE* with the stars, to avoid conflict
with lexical variables) and you want to store into
them based on runtime calculation, then use SET.
? (defparameter *foo* 1)
*FOO*
? (defparameter *bar* 2)
*BAR*
? *foo*
1
? (SET (first (list '*foo* '*bar*)) 42)
42
? *foo*
42
>
> So even though this - (car (symbol-bundle 2 (list 'listx *counta*))) -
> returns listsx1, and setf doesn't return any errors, when I check to
> see if listx1 was changed, it wasn't.
>
> If anybody has any ideas why setf is working this way, I would very
> much appreciate it. It would be a big relief to me to finish this
> "program" and use it in a multitude of ways, and I would be happy to
> make the code available, as simple as it is.
>
> Also - are there simple ways of automatically creating incremented
> variable names? I tried intern on strings but that didn't work too
> well, and settled on my current method.
(defparameter *my-symbol-counter* 0)
(defun make-symbol-plus-counter (&optional (name "FOO")
(package *package*)
(counter '*my-symbol-counter*))
(prog1 (intern (concatenate 'string
name
(princ-to-string (symbol-value counter)))
package)
(incf (symbol-value counter))))
? (MAKE-SYMBOL-PLUS-COUNTER "BAR")
BAR10
? (MAKE-SYMBOL-PLUS-COUNTER "BAR")
BAR11
? (MAKE-SYMBOL-PLUS-COUNTER "BAR")
BAR12
? (MAKE-SYMBOL-PLUS-COUNTER)
FOO13
>
> Thank you,
> Eric Belcastro
--
http://lispm.dyndns.org/
Ahhh. Thank you very much for that lesson - I am excited to get to
back to work on it now - and I am going to replace the old recursive
variable name creation with a modified version of what you
demonstrated.
Looking forward to learning more in the future.
Eric
Rainer Joswig <······@lisp.de> wrote:
+---------------
| Eric <·············@gmail.com> wrote:
| > Because any number of ratios may be input, I am automatically creating
| > variables and assigning names to them. I am doing it like this...
...
| > Also - are there simple ways of automatically creating incremented
| > variable names? I tried intern on strings but that didn't work too
| > well, and settled on my current method.
|
| (defparameter *my-symbol-counter* 0)
| (defun make-symbol-plus-counter (&optional (name "FOO")
| (package *package*)
| (counter '*my-symbol-counter*))
| (prog1 (intern (concatenate 'string
| name
| (princ-to-string (symbol-value counter)))
| package)
| (incf (symbol-value counter))))
+---------------
You showed him how to do it, but you forgot to tell him *NOT TO*!! ;-}
That's right, Eric, *don't* do this. Instead, define yourself *one*
global variable that hold either an adjustable array or a hash table
(or some kind of tree structure, whatever) that can be grown dynamically
and be quickly indexed by your "counter" numbers, e.g.:
> (defvar *lists* (make-array 20 :adjustable t :fill-pointer 0))
*lists*
> (defun add-new-list (list)
(vector-push-extend list *lists*
;; exponential growth [Fibonacci might be better]
(array-dimension *lists* 0)))
ADD-NEW-LIST
> (add-new-list '(a a b a))
0
> (add-new-list '(c d c d e e))
1
> (add-new-list '(f g h))
2
> (length *lists*)
3
> *lists*
#((A A B A) (C D C D E E) (F G H))
> (aref *lists* 1) ; fast access to any one
(C D C D E E)
> (map 'list #'length *lists*) ; can use sequence functions
(4 6 3)
> (apply #'lcm *)
12
>
That is, having inserted a number of lists of varying lengths,
it's rather simple to "mine" the data and find out, say, the
least common multiple of their lengths [which is sometimes
something you might want to know about a series of patterns].
Let's add 100 more lists, and see what happens:
> (loop for i below 200 by 2 do
(add-new-list (list i (1+ i)) ))
NIL
> (length *lists*) ; the "active" length (fill pointer)
103
> (array-dimension *lists* 0) ; the total length
160
> (let ((*print-length* 8))
(print *lists*)
nil)
#((A A B A) (C D C D E E) (F G H) (0 1) (2 3) (4 5) (6 7) (8 9) ...)
NIL
> (aref *lists* 97) ; fast access to any one
(188 189)
>
The array has only been resized three times (doubling each time),
so the number of resizings per insertion can be made as small as
you like.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
I am actually going to spend an hour or three working on some of the
things you brought up in your post, Rob. There are some pretty
fundamental things that you bring up that I am going to need to work
with repeatedly in the future, so I might as well understand them as
best as I can now. At the moment I am using one global array that is
constantly being referenced and only storing singular lists in the
variables that are being created that I extract from various
operations on the array. Working with the singular global variable
assigned to an adjustable array was somewhat similar to what Peter
Seibel was hinting at in the chapter on arrays and hash tables in
Practical Common Lisp, but I kind of brushed past it too quickly
because I was in a rush to get started. I've got a lot to learn, and
it's nice to see such a great community of lisp users here.
Out of curiosity - I keep creating new functions for a specific task,
some work, some don't, and some have limitations...but I have a
feeling there is a much easier way than I am currently going about it
and want to make the code a bit more elegant.
Say I want to create a function that fills a list of length n with a
sequence that counts from 1 to n, at a given interval r and returns
the list. And this process being generalized for any given length or
interval. Of course the length and interval have to be relatively
prime.
For example: If the interval is 3 and the length is 17, the list
returned would be...
(1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
You can see that, since the interval is 3, if you read every 3 in the
final list you will see 1 2 3 4...etc.
I have done this several different ways, but ran into some
limitations, and am now back to work on a better way. Any
suggestions? I have a feeling it is much simpler than I am making it.
I first did it with vectors then with lists.
In article
<····································@e23g2000prf.googlegroups.com>,
Eric <·············@gmail.com> wrote:
> Out of curiosity - I keep creating new functions for a specific task,
> some work, some don't, and some have limitations...but I have a
> feeling there is a much easier way than I am currently going about it
> and want to make the code a bit more elegant.
>
> Say I want to create a function that fills a list of length n with a
> sequence that counts from 1 to n, at a given interval r and returns
> the list. And this process being generalized for any given length or
> interval. Of course the length and interval have to be relatively
> prime.
>
> For example: If the interval is 3 and the length is 17, the list
> returned would be...
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> You can see that, since the interval is 3, if you read every 3 in the
> final list you will see 1 2 3 4...etc.
>
> I have done this several different ways, but ran into some
> limitations, and am now back to work on a better way. Any
> suggestions? I have a feeling it is much simpler than I am making it.
> I first did it with vectors then with lists.
There are two questions:
* what kind of implementation strategy do you want to use?
* how to code above efficiently in Lisp?
Did you read Abelson & Sussman, SICP? The book describes
how to solve this class of problems using the Lisp dialect Scheme.
There are some basic tools to learn.
One idea would be for example to create three lists
(1 .. 6, 7 .. 12, 13 .. 17) and zip them together into
one list.
Another one would be to be able to compute the next element
from a start element and just call this length - 1 times,
collecting the elements.
Another one would be to use some functional combination
to create the sequence of items.
Another one would be to create the list (or vector)
and iterate three interval times over it incrementing
a counter and setting the element.
Let's see! - Lisp striptease time - show some code! ;-)
--
http://lispm.dyndns.org/
> Let's see! - Lisp striptease time - show some code! ;-)
>
> --http://lispm.dyndns.org/
*cue the music
*cue the lights
*oh...oh my goodness, that is some ugly code.
*oh well, she means well. It's her first time.
*...
*she's got a nice lexical closure, though.
Here is a portion of the code...
(Though you can skip over all of it and go to the bottom to see what
is
pertinent to my question)
;;list-a-scale just creates a list of ordered integers from n up to x
;;(I already wrote a count-up function and will probably just use a
;;modified version of that in the final code)
;;
;;(defun count-up (n)
;; (cond ((= n 1) (list 1))
;; (t (append (count-up (- n 1)) (list n)))))
;;
;;symbol-scroll scrolls the list to the left or right
;;reorder-by-n takes every n element of the list, and returns a new
;;list - which sounds similar to what I want, but it's not.
;;
;;The given portion of the code here creates listx1 listx2 .... listxn
;;automatically - these lists contain all numbers that are equivalent
;;in the final structure - and they will be called while *countera*
is
;;being decremented in the final function and translated to the final
list.
;;
;;create-ssarray is the part that I am concentrated on now - r1 is the
ratio
;;of similarity, sp1 is the starting point for that ratio (it can
start
;;anywhere instead of at just 1), slength is the length of the list
;;(1 2 3 4...). Everything works perfectly for ratios
;;2,3,6,etc. but not for many other ratios as the pattern I am using
is
;;faulty, and I know why. I just have to start over.
(setf *numratios* 1)
(setf clm 0)
(setf *counta* 0)
(defun ordered-union (x y)
(append x (remove-if #'(lambda (k) (member k x)) y)))
(defun create-ssarray (slength r1 sp1)
(let* ((original-list-t (list-a-scale 1 slength))
(new-list-1 (symbol-scroll (- sp1 1)
(reorder-by-n (ceiling
(/ slength r1))
original-list-t))))
(setf ssarray (build-array (list original-list-t new-list-1)))
(setf *original-list* (list-a-scale 1 slength))
(create-sublists ssarray)))
(defun create-sublists (array)
(incf *counta*)
(set (car (symbol-bundle 2 (list 'listx *counta*)))
(listrec (pick-array 0 clm (+ *numratios* 1) array :down) 1))
(cond ((check-length *counta*) nil)
(t (setf clm (setclm *counta*)) (create-sublists array))))
(defun listrec (listx n)
(if (equal n 1) (setf listg (remove-duplicates (ordered-union listx
(pick-array 0 (- (nth n listx) 1) (+ *numratios* 1)
ssarray :down))))
(setf listg (remove-duplicates (ordered-union listg
(pick-array 0 (- (nth n listg) 1) (+ *numratios* 1)
ssarray :down)))))
(cond ((null (nth (+ n 1) listg)) listg)
(t (listrec listg (+ n 1)))))
(defun check-length (n)
(if (equal n 1) (equal (length listx1) (length *original-list*))
(equal (length (append-lists n)) (length *original-
list*))))
(defun append-lists (n)
(cond ((equal n 0) nil)
(t (append (symbol-value (car (symbol-bundle 2 (list 'listx
n))))
(append-lists (- n 1))))))
(defun setclm (n)
(let ((listo (sort (append-lists n) '<)))
(- (find-if #'(lambda (x) (null (equal x (nth (- x 1) listo))))
*original-list*) 1 )))
;;I am thinking about doing it by creating a positional-list that
contains
;;the positions in the list that need replaced by 1 2 3 4 5...
;;
;;(positional-list (mapcar #'(lambda (x) (+ (mod (* x r1) slength) 1))
;; (list-a-scale 0 slength)))
;;
;;I would then need to take this positional-list and a *original-list*
of (1 2 3...)
;;
;;(setf *original-list* (list-a-scale 1 slength))
;;
;;integers in counting order and say (with code) take the first number
from
;;counting-list and put it in a new list in the position that is the
first number
;;in positional-list. Then take the second number from counting list
and put it
;;in a new list in the position that is the second number in position-
list, etc.
;;
;;I am trying to do this with nth mapcar and replace now...maybe using
an empty
;;vector filled with 0s (build-array) and putv and then converting
back to list
;;would be better, don't know.
;;
;;Regardless, thank you everyone for so much help. I'll try to
educate myself
;;and not be such a needy little boy.
In article
<····································@t1g2000pra.googlegroups.com>,
Eric <·············@gmail.com> wrote:
Some comments about the general style of your code below:
>
> ;;list-a-scale just creates a list of ordered integers from n up to x
> ;;(I already wrote a count-up function and will probably just use a
> ;;modified version of that in the final code)
> ;;
> ;;(defun count-up (n)
> ;; (cond ((= n 1) (list 1))
> ;; (t (append (count-up (- n 1)) (list n)))))
APPEND is always a warning sign. APPEND in recursive
functions supposed to be inefficient. APPEND creates
a fresh list - always. Your code is maximum inefficient,
since you append a long list to a list with a single item.
Rethink it.
> ;;
> ;;symbol-scroll scrolls the list to the left or right
> ;;reorder-by-n takes every n element of the list, and returns a new
> ;;list - which sounds similar to what I want, but it's not.
> ;;
> ;;The given portion of the code here creates listx1 listx2 .... listxn
> ;;automatically - these lists contain all numbers that are equivalent
> ;;in the final structure - and they will be called while *countera* is
> ;;being decremented in the final function and translated to the final list.
> ;;
> ;;create-ssarray is the part that I am concentrated on now - r1 is the ratio
> ;;of similarity, sp1 is the starting point for that ratio (it can start
> ;;anywhere instead of at just 1), slength is the length of the list
> ;;(1 2 3 4...). Everything works perfectly for ratios
> ;;2,3,6,etc. but not for many other ratios as the pattern I am using is
> ;;faulty, and I know why. I just have to start over.
>
> (setf *numratios* 1)
> (setf clm 0)
> (setf *counta* 0)
Global variables should always be written as *foo*. Variables
are introduced by DEFPARAMETER. Hint: DEFPARAMETER allows
a comment string.
(defparameter *foo* 'bar
"*FOO* is the prototypical variable")
>
> (defun ordered-union (x y)
> (append x (remove-if #'(lambda (k) (member k x))
> y)))
I would give x and y more descriptive names. Add a comment.
(defun foo (bar)
"the function foo does..."
ghsdf)
Any good Common Lisp allows you to look up the documentation string
with a key combination. Also many implementations will
show you the arglist when you press space after a function
or if you press some key combination. You want then
variable names that are readable. Otherwise you
would see (setclm n) - what does it mean? You likely will
not remember what the function does after a week not looking
at the code.
>
> (defun create-ssarray (slength r1 sp1)
> (let* ((original-list-t (list-a-scale 1 slength))
> (new-list-1 (symbol-scroll (- sp1 1)
> (reorder-by-n (ceiling (/ slength r1))
> original-list-t))))
> (setf ssarray (build-array (list original-list-t new-list-1)))
> (setf *original-list* (list-a-scale 1 slength))
> (create-sublists ssarray)))
I would not even guess what the function does. It is not descriptive
enough. Any Lisp compiler (also interactive) would also complain
that ssarray is not known to be a variable - it is not introduced
in this function. Using global variables like *original-list*
is also not a good idea. Rule: avoid global variables.
>
> (defun create-sublists (array)
> (incf *counta*)
> (set (car (symbol-bundle 2 (list 'listx *counta*)))
> (listrec (pick-array 0 clm (+ *numratios* 1) array :down) 1))
> (cond ((check-length *counta*) nil)
> (t (setf clm (setclm *counta*)) (create-sublists array))))
Again it is not clear what this does.
You definitely need more documentation.
I also put either examples in the documentation or write tests.
(defun append-foo (list)
"Append the symbol foo to the end of the input list."
(append list (list 'foo)))
; (append-foo '(1 2 3))
; -> (1 2 3 FOO)
Any good Lisp editor lets you execute the code in the comment.
A typical thing would to select the code with a double click
and press eval-region. Sometimes you also can place the
cursor at the end or the beginning of a form and press enter.
Even if the form is in the comment.
Sometimes I just use the editor and no listener.
The code is in the editor buffer and example calls are in the comments.
When I develop the function, I execute the code in the comment to
see if it works. If the tests get more complicated, I write tests
and execute those from forms in the comments.
(defun listrec (listx n)
(if (equal n 1)
(setf listg (remove-duplicates (ordered-union listx (pick-array 0 (- (nth n listx) 1) (+ *numratios* 1) ssarray :down))))
(setf listg (remove-duplicates (ordered-union listg (pick-array 0 (- (nth n listg) 1) (+ *numratios* 1) ssarray :down)))))
(cond ((null (nth (+ n 1) listg)) listg)
(t (listrec listg (+ n 1)))))
Again you set a symbol not defined in the function (listg). You really should
use the compiler for development. Find out what the keychord your
editor has for 'compile defun'. The you can have the cursor somewhere in
the function and the editor will pick the whole function, compile
it with the compiler and present any output. The compiler would
complain about free variables, missing arguments, ... and many
similar errors. If you have a good compiler, you even might get
style warnings or efficiency hints.
> (defun check-length (n)
> (if (equal n 1) (equal (length listx1) (length *original-list*))
> (equal (length (append-lists n)) (length
> *original-list*))))
Somehow I find above function not intuitive. You are using global variables.
Don't do that.
>
> (defun append-lists (n)
> (cond ((equal n 0) nil)
> (t (append (symbol-value (car (symbol-bundle 2 (list 'listx n))))
> (append-lists (- n 1))))))
Again, a recursive append. Again some access to an outside datastructure.
>
> (defun setclm (n)
> (let ((listo (sort (append-lists n) '<)))
> (- (find-if #'(lambda (x) (null (equal x (nth (- x 1) listo))))
> *original-list*) 1 )))
>
Again a global variable used.
I think you should write your code in small pieces that work independently.
Avoid side effects. Make each function a little 'module' which
takes input (only the arglist, no global variables) and create
output. Make them easily testable - independently. Each function
should have a clear and documented purpose. Make them easy
to combine.
Rewrite the functions. Do it again. Until you like what you see.
Especially for beginners with Lisp it is important to experiment
and to try out alternatives. Lisp is very good for interactively
designing implementations of algorithms. You can change it and
test it immediately. Also reading some books on basic usage
of Lisp lets you learn from others - SICP, PAIP, Lisp (3rd Edition,
Winston/Horn, Practical Common Lisp, ...
It takes some time, but suddenly it will all fit together.
If you read and understand AMOP, even enlightenment is possible. ;-)
>
>
> ;;I am thinking about doing it by creating a positional-list that contains
> ;;the positions in the list that need replaced by 1 2 3 4 5...
> ;;
> ;;(positional-list (mapcar #'(lambda (x) (+ (mod (* x r1) slength) 1))
> ;; (list-a-scale 0 slength)))
> ;;
> ;;I would then need to take this positional-list and a *original-list* of (1
> 2 3...)
> ;;
> ;;(setf *original-list* (list-a-scale 1 slength))
> ;;
> ;;integers in counting order and say (with code) take the first number from
> ;;counting-list and put it in a new list in the position that is the first
> number
> ;;in positional-list. Then take the second number from counting list and put
> it
> ;;in a new list in the position that is the second number in position-list,
> etc.
> ;;
> ;;I am trying to do this with nth mapcar and replace now...maybe using an
> empty
> ;;vector filled with 0s (build-array) and putv and then converting back to
> list
> ;;would be better, don't know.
> ;;
> ;;Regardless, thank you everyone for so much help. I'll try to educate
> myself
> ;;and not be such a needy little boy.
--
http://lispm.dyndns.org/
> I think you should write your code in small pieces that work independently.
> Avoid side effects. Make each function a little 'module' which
> takes input (only the arglist, no global variables) and create
> output. Make them easily testable - independently. Each function
> should have a clear and documented purpose. Make them easy
> to combine.
Thank you Rainer. Even though this was my first attempt and I am
planning on rewriting everything a few times to the point where it
feels right, I would have continually made the same mistakes even in
the refinements without your words of wisdom and the help of the
others. Though the final code I came up with worked accurately in
terms of the final result, it eventually caused a stack overflow for
long lengths of 9999 or longer, because of the inefficient use of
recursive calls to append, and the incremented global variables, lack
of documentation, etc. would have definitely confused me a few months
from now. Also, I want the code to complete within itself without
calls to functions not standardized across lisp implementations, so
that I can eventually upload all of the stuff I create for others to
use (probably of use to musicians working with
Common Music and Symbolic Composer) when it is done well enough.
I played around with C and some other programming languages when I was
younger, but felt they were
so utterly conceptually disconnected from any sort of smooth flow of
how I would think of something to how I would create it in code. So I
gave them up, busy with other studies, and it wasn't until I found
Lisp, in this case Common LISP, that I actually felt like a
programming language made conceptual sense to me. I am busy with
studying physics, but hope to still really learn how to continue to
create in Lisp, and do so the right way, with practice.
From: Holger Schauer
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <yxzmysib8xt.fsf@gmx.de>
On 5212 September 1993, Rainer Joswig wrote:
> APPEND is always a warning sign. APPEND in recursive
> functions supposed to be inefficient. APPEND creates
> a fresh list - always. Your code is maximum inefficient,
> since you append a long list to a list with a single item.
The typical idiom for using append is the following, isn't it?
(setq reversedresult (append (list singleitem) reversedresult)
;; do something with it, finally ...
(reverse reversedresult)
I'm just curious because of your broad claim of inefficency of append:
what else would you propose?
Holger
--
--- http://hillview.bugwriter.net/ ---
"Die Wiederkehr eines gesamtdeutschen Parlaments nach Berlin und der
kriegerische Konflikt um den Kosovo haben eine gemeinsame Ursache,
das Ende des Kommunismus."
-- Wolfgang Thierse, Bundestagspraesident
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> On 5212 September 1993, Rainer Joswig wrote:
> > APPEND is always a warning sign. APPEND in recursive
> > functions supposed to be inefficient. APPEND creates
> > a fresh list - always. Your code is maximum inefficient,
> > since you append a long list to a list with a single item.
>
> The typical idiom for using append is the following, isn't it?
>
> (setq reversedresult (append (list singleitem) reversedresult)
> ;; do something with it, finally ...
I have not seen that. Most people just use CONS.
(equal
(CONS 'a '(b c d))
(append (list 'a) '(b c d)))
The only difference is that the first form is a bit
more efficient, since it just CONSes one cons.
The APPEND form creates copies the first list into
a fresh new list.
> (reverse reversedresult)
>
> I'm just curious because of your broad claim of inefficency of append:
> what else would you propose?
The 'problematic' use of APPEND is because the first arguments
(minus the last one) are copied. ALL.
(APPEND long-list-1 .. long-list-n (list 'foo))
means that all long-list-1 .. long-list-n are copied.
If you need to append them, that's fine. But be
careful in recursive algorithms where the
recursive call is in the first arguments (minus the last one).
(defun foo-l (n)
"VERY BAD!!!"
(if (zerop n)
'()
(append (foo-l (1- n))
(list n))))
(defun foo-r (n)
(labels ((foo-r-aux (i)
(if (> i n)
nil
(cons i (foo-r-aux (1+ i))))))
(foo-r-aux 1)))
Both functions are doing the same.
Let's trace the APPEND version:
? (foo-l 10)
0> Calling (MY-APPEND NIL (1))
<0 MY-APPEND returned (1)
0> Calling (MY-APPEND (1) (2))
<0 MY-APPEND returned (1 2)
0> Calling (MY-APPEND (1 2) (3))
<0 MY-APPEND returned (1 2 3)
0> Calling (MY-APPEND (1 2 3) (4))
<0 MY-APPEND returned (1 2 3 4)
0> Calling (MY-APPEND (1 2 3 4) (5))
<0 MY-APPEND returned (1 2 3 4 5)
0> Calling (MY-APPEND (1 2 3 4 5) (6))
<0 MY-APPEND returned (1 2 3 4 5 6)
0> Calling (MY-APPEND (1 2 3 4 5 6) (7))
<0 MY-APPEND returned (1 2 3 4 5 6 7)
0> Calling (MY-APPEND (1 2 3 4 5 6 7) (8))
<0 MY-APPEND returned (1 2 3 4 5 6 7 8)
0> Calling (MY-APPEND (1 2 3 4 5 6 7 8) (9))
<0 MY-APPEND returned (1 2 3 4 5 6 7 8 9)
0> Calling (MY-APPEND (1 2 3 4 5 6 7 8 9) (10))
<0 MY-APPEND returned (1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
It is called ten times. Ten times it makes a
fresh copy of its first argument.
Stuff like that was the reason for Perlis saying
that the Lisp programmer knows the value of
everything, but the cost of nothing.
The CONS version just calls CONS to allocate
n conses.
>
> Holger
--
http://lispm.dyndns.org/
From: Holger Schauer
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <yxztzmq6r5p.fsf@gmx.de>
On 5213 September 1993, Rainer Joswig wrote:
> In article <···············@gmx.de>,
> Holger Schauer <··············@gmx.de> wrote:
>> The typical idiom for using append is the following, isn't it?
>> (setq reversedresult (append (list singleitem) reversedresult)
> I have not seen that. Most people just use CONS.
> (equal
> (CONS 'a '(b c d))
> (append (list 'a) '(b c d)))
Yes, right. I was somehow too fixated on discussing append. Hmm, I
can't remember where I learned about that "idiom". Maybe it's a Prolog
thing, but that's not very likely either. Perhaps I was just confusing
append and cons wrt. the idiom.
> The only difference is that the first form is a bit
> more efficient, since it just CONSes one cons.
> The APPEND form creates copies the first list into
> a fresh new list.
I was only thinking about traversing the first list to find the last
cons cell to use for appending. Thanks for reminding me of the copying
issue. A penny saved is a penny earned.
> means that all long-list-1 .. long-list-n are copied.
> If you need to append them, that's fine. But be
> careful in recursive algorithms where the
> recursive call is in the first arguments (minus the last one).
Sure. Although CL doesn't promise tail call optimization, most
implementations do, AFAIK. So avoiding using append on the result of a
recursive call follows from the general advice to try to come up with
tail-recursive algorithms (if you're using recursion at all, of
course).
Holger
--
--- http://hillview.bugwriter.net/ ---
"Verwende Perl. Shell will man koennen, dann aber nicht verwenden."
-- Kristian Koehntopp in de.comp.os.unix.misc
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> On 5213 September 1993, Rainer Joswig wrote:
> > In article <···············@gmx.de>,
> > Holger Schauer <··············@gmx.de> wrote:
> >> The typical idiom for using append is the following, isn't it?
> >> (setq reversedresult (append (list singleitem) reversedresult)
> > I have not seen that. Most people just use CONS.
> > (equal
> > (CONS 'a '(b c d))
> > (append (list 'a) '(b c d)))
>
> Yes, right. I was somehow too fixated on discussing append. Hmm, I
> can't remember where I learned about that "idiom". Maybe it's a Prolog
> thing, but that's not very likely either. Perhaps I was just confusing
> append and cons wrt. the idiom.
>
> > The only difference is that the first form is a bit
> > more efficient, since it just CONSes one cons.
> > The APPEND form creates copies the first list into
> > a fresh new list.
>
> I was only thinking about traversing the first list to find the last
> cons cell to use for appending. Thanks for reminding me of the copying
> issue. A penny saved is a penny earned.
>
> > means that all long-list-1 .. long-list-n are copied.
> > If you need to append them, that's fine. But be
> > careful in recursive algorithms where the
> > recursive call is in the first arguments (minus the last one).
>
> Sure. Although CL doesn't promise tail call optimization, most
> implementations do, AFAIK. So avoiding using append on the result of a
> recursive call follows from the general advice to try to come up with
> tail-recursive algorithms (if you're using recursion at all, of
> course).
Right.
(defun foo ...
...
(append (foo ...) ...))
(FOO ...) is not a tail call. But the issue is that
calling APPEND on lists in recursive functions
can make the complexity of the function to be n^2.
Means, for inputs of ten or hundred items it may not be
an issue, but if n gets 1000 or more you see lots
of cons operations going on. Wasted also, since most
create temporary objects that will be GCed.
BUT:
Hmm, I would avoid tail-recursive code in Common Lisp if possible.
The language Common Lisp was not designed with tail-call
optimization in mind. The way to get a compiler to optimize a tail-call
is clumsy in most implementations - the amount of
optimizations differ from implementation to implementation.
Plus debugging gets harder. Plus it may be different
when you run the code in the interpreter.
LispWorks:
http://www.lispworks.com/documentation/lw50/LWUG/html/lwuser-98.htm#pgfId-889221
Tail call optimization when DEBUG<3 (see the restrictions)
The DEBUG declaration is used to turn that on/off in compiled (!)
code. That alone is clumsy.
Say, I want full debugging, but tail call optimization turned
on. What now? Insert LOCALLY declarations?
The biggest problem I see is that tail call optimizations
has various restrictions (REST args, Dynamic Variables, ...),
so that it is not obvious from staring at the code, what
the compiler will do. Will the call be optimized or not?
Difficult to say! You have to analyze the code carefully,
look at the disassembly or try to see the effect by
running some test data -> UGLY.
I would say, avoid tail call optimization.
Use a plain old iteration construct (DOLIST, DOTIMES, LOOP, ITERATE).
You want to list integers from 1 to n?
(loop for i from 1 upto n collect i)
No need for tail-call optimization. Just use a plain LOOP.
It gets more problematic with graph traversal and other
things, but the typical loop is a good candidate
to be written as a LOOP and not as a tail-recursive
function.
A few friends of mine have written an extremely complicated piece
of software. They are using tail call optimization.
Their software would not run without it. I tried to
tell them that this is not a good idea. But they don't listen. ;-)
For them the optimization helped to code their complex algorithms.
But then, there is no chance that this code will run on
the Lisp Machine, though they still have one - since the
Lisp Machine compiler does not support it. ;-)
>
> Holger
From: Holger Schauer
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <yxz8x418qt3.fsf@gmx.de>
On 5214 September 1993, Rainer Joswig wrote:
> Hmm, I would avoid tail-recursive code in Common Lisp if possible.
I sometimes find it hard to come up with a straight-forward
formulation in iterative terms for an inherent recursive problem. I
am also usually much more concerned about maintainability and
readability than about speed, so usually when a recursive solution is
more straight forward to me, I won't consider an iterative
reformulation.
> The language Common Lisp was not designed with tail-call
> optimization in mind. The way to get a compiler to optimize a tail-call
> is clumsy in most implementations - the amount of
> optimizations differ from implementation to implementation.
I would be interested to learn about what the different
implementations do. Maybe that would be a nice addition to Daniel
Weinrebs recently published lisp (implementations) survey.
> The DEBUG declaration is used to turn that on/off in compiled (!)
> code. That alone is clumsy. Say, I want full debugging, but tail
> call optimization turned on.
That's the usual speed/debug trade-off, isn't it? I would go for full
debugging during development and for full speed when in production. I
can see why having full debugging and full speed at the same time is a
worthy goal, but it seems clear to me that all optimizations for some
use case probably come at a price.
> It gets more problematic with graph traversal and other
> things, but the typical loop is a good candidate
> to be written as a LOOP and not as a tail-recursive
> function.
I agree. But it's still a matter of one's focus (readability,
speed and/or debugging issues) which way to go. I'm quite neutral to
the issue in general.
> A few friends of mine have written an extremely complicated piece
> of software. They are using tail call optimization.
> Their software would not run without it.
That's always a bad sign. Tail call optimization is an optimization,
not a problem solution. Of course, if you know what you're doing and
that you can and want to rely on that particular optimization, you're
free to exploit it being available, but otherwise (i.e., your code
runs only by chance and breaks under, say, different debug settings) I
would say the code is buggy (as in "inappropriate for the input data")
and suggest trying different approaches.
Holger
--
--- http://hillview.bugwriter.net/ ---
"If you're so special, then why aren't you dead?"
-- Breeders, "I just wanna get along"
From: Duane Rettig
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <o0odcxm9rm.fsf@gemini.franz.com>
Holger Schauer <··············@gmx.de> writes:
> On 5214 September 1993, Rainer Joswig wrote:
>> Hmm, I would avoid tail-recursive code in Common Lisp if possible.
>
>> The DEBUG declaration is used to turn that on/off in compiled (!)
>> code. That alone is clumsy. Say, I want full debugging, but tail
>> call optimization turned on.
>
> That's the usual speed/debug trade-off, isn't it?
No, it is a stack-space vs debug tradeoff, mostly. Not all tail-call
merging operations are optimizations in terms of time - that's why I
don't like to call them "tail-call-optimization", because the usual
thing one thinks of when hearing the word "optimization" is "speed".
> I would go for full
> debugging during development and for full speed when in production. I
> can see why having full debugging and full speed at the same time is a
> worthy goal, but it seems clear to me that all optimizations for some
> use case probably come at a price.
The optimization and the price are along different axes. And in fact,
the tendency is to desire different tradeoffs for when a function
calls itself in tail-position and when a function calls another
function in tail-position. In Allegro CL, we separate the two cases,
allowing the control of each with compiler switches:
http://www.franz.com/support/documentation/8.1/doc/variables/compiler/tail-call-self-merge-switch.htm
http://www.franz.com/support/documentation/8.1/doc/variables/compiler/tail-call-non-self-merge-switch.htm
And since by default lisps built for development have a debug setting
of 2 and for production a debug setting of 1, the defaults tend to
follow the preferences of the majority of users, without removing the
capability to customize.
>> A few friends of mine have written an extremely complicated piece
>> of software. They are using tail call optimization.
>> Their software would not run without it.
>
> That's always a bad sign. Tail call optimization is an optimization,
> not a problem solution.
It is an optimization on stack space. Whether it is a problem
solution depends on whether stack is a limited resource in your app.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> On 5214 September 1993, Rainer Joswig wrote:
> > Hmm, I would avoid tail-recursive code in Common Lisp if possible.
>
> I sometimes find it hard to come up with a straight-forward
> formulation in iterative terms for an inherent recursive problem. I
> am also usually much more concerned about maintainability and
> readability than about speed, so usually when a recursive solution is
> more straight forward to me, I won't consider an iterative
> reformulation.
>
> > The language Common Lisp was not designed with tail-call
> > optimization in mind. The way to get a compiler to optimize a tail-call
> > is clumsy in most implementations - the amount of
> > optimizations differ from implementation to implementation.
>
> I would be interested to learn about what the different
> implementations do. Maybe that would be a nice addition to Daniel
> Weinrebs recently published lisp (implementations) survey.
There are many more things to compare. That would be
a much much longer paper.
> > The DEBUG declaration is used to turn that on/off in compiled (!)
> > code. That alone is clumsy. Say, I want full debugging, but tail
> > call optimization turned on.
>
> That's the usual speed/debug trade-off, isn't it? I would go for full
> debugging during development and for full speed when in production. I
> can see why having full debugging and full speed at the same time is a
> worthy goal, but it seems clear to me that all optimizations for some
> use case probably come at a price.
Speed and Debug are different optimization angles.
Tail-call elimination is not a simple optimization
for speed or something that reduces debuggability.
It changes the semantics of the language in a big way.
It interacts with other parts of the program in a big way.
In Common Lisp it has to interact with condition handling,
special variables, rest arguments, and other stuff.
Unless there is a meaningful description how tail
call elimination fits into the language model, I would
not use it without really closely looking at the source
code and inspecting what the compiler does. Especially since
every compiler does something different for such an
unspecified language change.
I also don't want 'full speed' in production. Don't optimize
for 'full speed'. Never. Only in places where it matters.
You want safety. Not speed. When you optimize for speed,
it means in Common Lisp, that many operations are unchecked,
and semantics of operations can change from the default.
Common Lisp compilers don't do much compile-time checking
(even SBCL/CMUCL does not get very far). You need
runtime checks otherwise errors go unnoticed and
your app will instead of handling errors just crash
or deliver results you don't expect. Common Lisp
has a totally different language model from a
language where everything is done so that you can
do as much checks as possible at compile-time.
Common Lisp programs will by DEFAULT be mostly unchecked
unless you have run them. Common Lisp compilers
will happily remove all kinds of checking and error
detection/reporting when you optimize for speed (and reduce
safety). The errors that one can introduce are some
subtle that you can spend ages to find them.
A 'full speed' deployed application will be very different
from a 'full debug' and 'full safety' app in development.
Most of the time 'full speed' is simply not necessary.
The default has to be to run with 'full safety'. IMHO, of course.
I also doubt that always the distinction between development
and deployment (which is also a bunch of very diverse situations)
is true. I, for example, want the ability from a deployed app to
* get meaningful backtraces
* replace and update code and data
* have full symbols at runtime
* trace code and get the output somewhere
* call a debugger and inspector to inspect
the runtime
and so on...
The buggy applications are not those where errors happen,
the buggy applications are those where you cannot handle
the errors due to unnecessary optimizations.
> > It gets more problematic with graph traversal and other
> > things, but the typical loop is a good candidate
> > to be written as a LOOP and not as a tail-recursive
> > function.
>
> I agree. But it's still a matter of one's focus (readability,
> speed and/or debugging issues) which way to go. I'm quite neutral to
> the issue in general.
>
> > A few friends of mine have written an extremely complicated piece
> > of software. They are using tail call optimization.
> > Their software would not run without it.
>
> That's always a bad sign. Tail call optimization is an optimization,
> not a problem solution.
As I said. It is not just an optimization. It is a change of
the semantics of a basic language construct (function calling)
and interacts with other elements of the language.
Common Lisp has special variables.
Simple example:
(defun foo (bar)
(let ((*foo* (something-here ...)))
...
(baz ...)))
*foo* is special. (baz ...) is possibly no longer a tail call.
Anything that sets up a scope that has to do something
when leaving it, is no longer an easy tail call.
You cannot just jump to the new place then.
You can't see from looking at the place in the source where the call is,
what it does. You have to inspect the source code around it and
also see what the compiler creates. Otherwise your code
might depend on the tail call elimination, but the
compiler was not able to do it.
> Of course, if you know what you're doing and
> that you can and want to rely on that particular optimization, you're
> free to exploit it being available, but otherwise (i.e., your code
> runs only by chance and breaks under, say, different debug settings) I
> would say the code is buggy (as in "inappropriate for the input data")
> and suggest trying different approaches.
>
> Holger
The most important thing to understand is that Common Lisp
by default is an dynamic language at runtime. Runtime does
not just mean development, but also deployment. The whole
package you get with the language is not only macros,
CLOS, compiler at runtime (all the things we like)
and so on - you also get no (or few/limited) compile-time checks.
What you know from a static language just does not apply.
You cannot optimize for 'full speed' (and lower safety, debug values)
and expect the program to do the same. It doesn't.
--
http://lispm.dyndns.org/
From: Holger Schauer
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <yxz63z58f1h.fsf@gmx.de>
(We have an interesting topic drift here -- from append to
optimizations. I really like that.)
On 5214 September 1993, Rainer Joswig wrote:
> Tail-call elimination is not a simple optimization
> for speed or something that reduces debuggability.
> It changes the semantics of the language in a big way.
> It interacts with other parts of the program in a big way.
> In Common Lisp it has to interact with condition handling,
> special variables, rest arguments, and other stuff.
I fail to see what you mean here. As far as I understand tail-call
optimization (and I'm sure I'm going to express it really badly),
you're just jumping to the recursive function without saving the
current "local" environment onto the stack. Whatever errors the
recursive function may throw or whatever condition handlers are
established should be the same, no? And for rest arguments, of course
you'll have to deal with them in the recursive function, but I don't
understand where this should be problematic. Probably my view on
tail-call optimization is way to naive.
> I also don't want 'full speed' in production. Don't optimize
> for 'full speed'. Never. Only in places where it matters.
Aka declare vs. proclaim. Sure. [...]
> Common Lisp has special variables.
> Simple example:
> (defun foo (bar)
> (let ((*foo* (something-here ...)))
> ...
> (baz ...)))
> *foo* is special. (baz ...) is possibly no longer a tail call.
> Anything that sets up a scope that has to do something
> when leaving it, is no longer an easy tail call.
> You cannot just jump to the new place then.
Could you elaborate? I can't see why you couldn't do a jump here.
I think I know what you're after here, but all you need to do is to
make *foo* available for access in the recursive calls to #'foo, but
this doesn't require you to keep a stack of environments you need to
unwind, does it? (I think your example would be clearer if you would
have a (declare (special *foo*)) inside #'foo (so that the needed
environment is established in foo), because otherwise *foo* as a
top-level special variable will be accessible in the environment
anyway.)
> You can't see from looking at the place in the source where the call is,
> what it does. You have to inspect the source code around it and
> also see what the compiler creates. Otherwise your code
> might depend on the tail call elimination, but the
> compiler was not able to do it.
I have trouble imagining source code that depends on tail call
elimination happening other than code that would blow up the stack
space. Or is that what you're talking about?
Holger
--
--- http://hillview.bugwriter.net/ ---
"If you're so special, then why aren't you dead?"
-- Breeders, "I just wanna get along"
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> (We have an interesting topic drift here -- from append to
> optimizations. I really like that.)
it was about the 'misuse' of append that leads
to poor performance...
>
> On 5214 September 1993, Rainer Joswig wrote:
> > Tail-call elimination is not a simple optimization
> > for speed or something that reduces debuggability.
> > It changes the semantics of the language in a big way.
> > It interacts with other parts of the program in a big way.
> > In Common Lisp it has to interact with condition handling,
> > special variables, rest arguments, and other stuff.
>
> I fail to see what you mean here. As far as I understand tail-call
> optimization (and I'm sure I'm going to express it really badly),
> you're just jumping to the recursive function without saving the
> current "local" environment onto the stack.
'tail calls' are not necessarily recursive.
(defun foo ()
(bar))
(defun bar ()
...)
(bar) is a tail call in FOO. No recursion involved.
If you do the tail call (and we have the optimization turned on),
FOO will never return. BAR will never return anything to FOO.
BAR will (unless it also has a tail call to another
function) return to the caller of FOO.
A tail call in a function is a call so that its return
value will not be used inside the function, other than just be
returned.
Note that also BAR could call FOO with a tail call
and you get mutual tail-recursive functions.
> Whatever errors the
> recursive function may throw or whatever condition handlers are
> established should be the same, no? And for rest arguments, of course
> you'll have to deal with them in the recursive function, but I don't
> understand where this should be problematic. Probably my view on
> tail-call optimization is way to naive.
>
> > I also don't want 'full speed' in production. Don't optimize
> > for 'full speed'. Never. Only in places where it matters.
>
> Aka declare vs. proclaim. Sure. [...]
>
> > Common Lisp has special variables.
> > Simple example:
> > (defun foo (bar)
> > (let ((*foo* (something-here ...)))
> > ...
> > (baz ...)))
> > *foo* is special. (baz ...) is possibly no longer a tail call.
> > Anything that sets up a scope that has to do something
> > when leaving it, is no longer an easy tail call.
> > You cannot just jump to the new place then.
>
> Could you elaborate? I can't see why you couldn't do a jump here.
Because you jump out of FOO - calling (BAR) - and you don't return to FOO.
How do you restore the special binding of *foo* that was
before the LET? Still you might need *FOO* inside BAZ.
> I think I know what you're after here, but all you need to do is to
> make *foo* available for access in the recursive calls to #'foo, but
> this doesn't require you to keep a stack of environments you need to
> unwind, does it? (I think your example would be clearer if you would
> have a (declare (special *foo*)) inside #'foo (so that the needed
> environment is established in foo), because otherwise *foo* as a
> top-level special variable will be accessible in the environment
> anyway.)
*FOO* can be rebound by any function it does not have to
be at the toplevel. If it is declared at top-level to
be special, then the code in any function has to look
it up in the dynamic environment and that can have
any number of bindings before. That in the source
code of that function there is no other binding means nothing, since
we are talking about dynamic binding and the function can be called
from any place at runtime.
> > You can't see from looking at the place in the source where the call is,
> > what it does. You have to inspect the source code around it and
> > also see what the compiler creates. Otherwise your code
> > might depend on the tail call elimination, but the
> > compiler was not able to do it.
>
> I have trouble imagining source code that depends on tail call
> elimination happening other than code that would blow up the stack
> space. Or is that what you're talking about?
>
> Holger
--
http://lispm.dyndns.org/
From: Holger Schauer
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <yxzprxcnk33.fsf@gmx.de>
On 5214 September 1993, Rainer Joswig wrote:
> In article <···············@gmx.de>,
> Holger Schauer <··············@gmx.de> wrote:
>> > Common Lisp has special variables.
>> > Simple example:
>> > (defun foo (bar)
>> > (let ((*foo* (something-here ...)))
>> > ...
>> > (baz ...)))
>> > *foo* is special. (baz ...) is possibly no longer a tail call.
>> > Anything that sets up a scope that has to do something
>> > when leaving it, is no longer an easy tail call.
>> > You cannot just jump to the new place then.
>> Could you elaborate? I can't see why you couldn't do a jump here.
> Because you jump out of FOO - calling (BAR) - and you don't return to FOO.
I assume you meant BAZ here, right?
> How do you restore the special binding of *foo* that was
> before the LET? Still you might need *FOO* inside BAZ.
Okay, I see. It's necessary to do extra house-tiding here for foo
(more exactly: for *foo* which is outside of baz) which one wants to
avoid when jumping.
Thanks for elaborating,
Holger
--
--- http://hillview.bugwriter.net/ ---
Fachbegriffe der Informatik - Einfach erkl�rt
145: Heavysidesche Sprungfunktion
Lernkurve eines Informatikers, der in einem Unternehmen mit
FDDI Backbone einen FI Sch�tz eingebaut hat. (Detlef Bosau)
In article <···············@gmx.de>,
Holger Schauer <··············@gmx.de> wrote:
> On 5214 September 1993, Rainer Joswig wrote:
> > In article <···············@gmx.de>,
> > Holger Schauer <··············@gmx.de> wrote:
>
> >> > Common Lisp has special variables.
> >> > Simple example:
> >> > (defun foo (bar)
> >> > (let ((*foo* (something-here ...)))
> >> > ...
> >> > (baz ...)))
> >> > *foo* is special. (baz ...) is possibly no longer a tail call.
> >> > Anything that sets up a scope that has to do something
> >> > when leaving it, is no longer an easy tail call.
> >> > You cannot just jump to the new place then.
>
> >> Could you elaborate? I can't see why you couldn't do a jump here.
>
> > Because you jump out of FOO - calling (BAR) - and you don't return to FOO.
>
> I assume you meant BAZ here, right?
Right. Sorry for the confusion. ;-)
>
> > How do you restore the special binding of *foo* that was
> > before the LET? Still you might need *FOO* inside BAZ.
>
> Okay, I see. It's necessary to do extra house-tiding here for foo
> (more exactly: for *foo* which is outside of baz) which one wants to
> avoid when jumping.
>
> Thanks for elaborating,
>
> Holger
--
http://lispm.dyndns.org/
Since your conversation brings up the issue, and since I am studying
the LOOP macro, is APPEND as a LOOP command (within the LOOP body) as
inefficient as APPEND in its normal sense outside of the LOOP macro?
Eric <·············@gmail.com> wrote:
+---------------
| Since your conversation brings up the issue, and since I am studying
| the LOOP macro, is APPEND as a LOOP command (within the LOOP body) as
| inefficient as APPEND in its normal sense outside of the LOOP macro?
+---------------
Probably not *quite* as inefficient, since most LOOP implementations
will cache a pointer to the tail of the result list being accumulated,
but some inefficiencies will still remain, since in the presence of
conditionals LOOP's APPEND has no way of knowing that a given list
being appended is going to be the "last" such piece, and thus will
COPY-LIST the last piece unnecessarily. And of course, it will also
have to copy all the earlier pieces as well. [Normal APPEND semantics.]
Using the NCONC keyword, when feasible, should save that copying.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Dec 8, 3:27 am, Eric <·············@gmail.com> wrote:
> Out of curiosity - I keep creating new functions for a specific task,
> some work, some don't, and some have limitations...but I have a
> feeling there is a much easier way than I am currently going about it
> and want to make the code a bit more elegant.
>
> Say I want to create a function that fills a list of length n with a
> sequence that counts from 1 to n, at a given interval r and returns
> the list. And this process being generalized for any given length or
> interval. Of course the length and interval have to be relatively
> prime.
>
> For example: If the interval is 3 and the length is 17, the list
> returned would be...
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> You can see that, since the interval is 3, if you read every 3 in the
> final list you will see 1 2 3 4...etc.
>
> I have done this several different ways, but ran into some
> limitations, and am now back to work on a better way. Any
> suggestions? I have a feeling it is much simpler than I am making it.
> I first did it with vectors then with lists.
I don't know if I understood you completely, but isn't the following
what you want?
;;; Untested
(defun fill-list-with-primes-scaled (n r)
(loop with r-primes = (primes-up-to r)
for i from 1 upto n by r
append (loop for p in r-primes
collect (+ n p))))
You can code this with a number of mutually recursive functions.
Cheers
--
Marco
Eric wrote:
> Out of curiosity - I keep creating new functions for a specific task,
> some work, some don't, and some have limitations...but I have a
> feeling there is a much easier way than I am currently going about it
> and want to make the code a bit more elegant.
>
> Say I want to create a function that fills a list of length n with a
> sequence that counts from 1 to n, at a given interval r and returns
> the list. And this process being generalized for any given length or
> interval. Of course the length and interval have to be relatively
> prime.
>
> For example: If the interval is 3 and the length is 17, the list
> returned would be...
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> You can see that, since the interval is 3, if you read every 3 in the
> final list you will see 1 2 3 4...etc.
>
> I have done this several different ways, but ran into some
> limitations, and am now back to work on a better way. Any
> suggestions? I have a feeling it is much simpler than I am making it.
> I first did it with vectors then with lists.
I suggest you post your unsatisfactory efforts explaining why you do not
like them.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On 2007-12-07 21:27:41 -0500, Eric <·············@gmail.com> said:
> For example: If the interval is 3 and the length is 17, the list
> returned would be...
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> You can see that, since the interval is 3, if you read every 3 in the
> final list you will see 1 2 3 4...etc.
>
> I have done this several different ways, but ran into some
> limitations, and am now back to work on a better way. Any
> suggestions? I have a feeling it is much simpler than I am making it.
> I first did it with vectors then with lists.
Not sure at what level you're working, so I apoligise if the commentary
seems too elementary:
? (defun wrap-list (&key length interval)
(loop
with wrap-vector = (make-array length)
for vector-index = 0 then (mod (+ vector-index interval) length)
for counter from 1 to length
do (setf (aref wrap-vector vector-index) counter)
finally
(return (loop for i across wrap-vector collect i))))
WRAP-LIST
? (wrap-list :length 17 :interval 3)
(1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
The key part is the (mod (+ vector-index interval) length)
If you get why that works the rest is bookkeeping.
regards,
Ralph
On Dec 8, 5:44 pm, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> On 2007-12-07 21:27:41 -0500, Eric <·············@gmail.com> said:
>
> > For example: If the interval is 3 and the length is 17, the list
> > returned would be...
> > (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> > You can see that, since the interval is 3, if you read every 3 in the
> > final list you will see 1 2 3 4...etc.
>
> > I have done this several different ways, but ran into some
> > limitations, and am now back to work on a better way. Any
> > suggestions? I have a feeling it is much simpler than I am making it.
> > I first did it with vectors then with lists.
>
> Not sure at what level you're working, so I apoligise if the commentary
> seems too elementary:
>
> ? (defun wrap-list (&key length interval)
> (loop
> with wrap-vector = (make-array length)
> for vector-index = 0 then (mod (+ vector-index interval) length)
> for counter from 1 to length
> do (setf (aref wrap-vector vector-index) counter)
> finally
> (return (loop for i across wrap-vector collect i))))
> WRAP-LIST
> ? (wrap-list :length 17 :interval 3)
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
>
> The key part is the (mod (+ vector-index interval) length)
> If you get why that works the rest is bookkeeping.
>
> regards,
>
> Ralph
Ahh...thank you Ralph, that is wonderful. It's funny too, because
I am sitting reading the DO, DOLIST, and LOOP sections of
Practical Common Lisp, and a Gentle Introduction to Symbolic
Computation, and wondering why I haven't used them more often,
and which one would be best. Well, thank you for the example,
it's a definite boost, and the last hurdle for this specific task.
Best Wishes,
Eric
Eric wrote:
> Out of curiosity - I keep creating new functions for a specific task,
> some work, some don't, and some have limitations...but I have a
> feeling there is a much easier way than I am currently going about it
> and want to make the code a bit more elegant.
>
> Say I want to create a function that fills a list of length n with a
> sequence that counts from 1 to n, at a given interval r and returns
> the list. And this process being generalized for any given length or
> interval. Of course the length and interval have to be relatively
> prime.
>
> For example: If the interval is 3 and the length is 17, the list
> returned would be...
> (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> You can see that, since the interval is 3, if you read every 3 in the
> final list you will see 1 2 3 4...etc.
>
> I have done this several different ways, but ran into some
> limitations, and am now back to work on a better way. Any
> suggestions? I have a feeling it is much simpler than I am making it.
Maybe?:
(let ((n 17)(i 3))
(loop with a = (make-array n)
for x below n
do (setf (svref a (mod (* i x) n)) (1+ x))
finally (return (coerce a 'list))))
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Eric <·············@gmail.com> wrote:
+---------------
| Say I want to create a function that fills a list of length n with a
| sequence that counts from 1 to n, at a given interval r and returns
| the list. And this process being generalized for any given length or
| interval. Of course the length and interval have to be relatively prime.
| For example: If the interval is 3 and the length is 17, the list
| returned would be...
| (1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
| You can see that, since the interval is 3, if you read
| every 3 in the final list you will see 1 2 3 4...etc.
+---------------
Spending a little time on theory up front often makes the resulting
program simpler in the end. First, let's do a small coordinate
transformation on your requirement into a domain that's a little
easier to deal with, specifially, seeking the desired permutation
of the numbers 0..N-1 rather than 1..N. [We can do a simple "fixup"
at the end.] Counting from zero is usually easier to deal with in such
matters, see <http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF>.
I use my version of IOTA a lot [doesn't everyone have one in
their toolbox]:
> (defun iota (count &optional (start 0) (step 1))
(loop repeat count for i upfrom start by step collect i))
IOTA
> (iota 17)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16)
> (iota 17 1)
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17)
> (iota 17 1 3)
(1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49)
>
Let's rename & extend this into an IOTA with a STRIDE [what you called
INTERVAL] modulo LENGTH using Ken Tilton's temporary array method
[shown in a parallel response]:
> (defun iota/mod/stride (length &key (start 0) (step 1) (stride 1))
(loop with temp-array = (make-array length)
repeat length
for val = start then (+ val step)
and index = 0 then (mod (+ index stride) length)
do (setf (svref temp-array index) val)
finally (return (coerce temp-array 'list))))
IOTA/MOD/STRIDE
> (iota/mod/stride 17 :stride 3 :start 1)
(1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> (iota/mod/stride 27 :stride 5 :start 1)
(1 12 23 7 18 2 13 24 8 19 3 14 25 9 20 4 15 26 10 21 5 16 27 11 22 6 17)
>
That's what we want, yes? Now let's see how to get rid of that ugly
temporary array... First, let's go back to counting from zero:
(iota/mod/stride 17 :stride 3)
(0 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11)
>
Observe that now the array INDEX is always (mod (* VAL STRIDE) LENGTH),
and *that* means that at the instant we store into array index 1, VAL
is the multiplicative inverse of STRIDE (mod LENGTH), by the definition
of multiplicative inverses:
X * X^(-1) = 1 (mod N)
So to get rid of the array, all we have to do is to find the
multiplicative inverse of STRIDE modulo LENGTH, and then we
simply generate the desired elements in order, this way:
> (defun iota/mod/stride (length &key (start 0) (stride 1))
(loop with stride^-1 = (reciprocal/mod stride length)
repeat length
for x = 0 then (mod (+ x stride^-1) length)
collect (+ x start)))
IOTA/MOD/STRIDE
> (iota/mod/stride 17 :stride 3 :start 1)
(1 7 13 2 8 14 3 9 15 4 10 16 5 11 17 6 12)
> (iota/mod/stride 27 :stride 5 :start 1)
(1 12 23 7 18 2 13 24 8 19 3 14 25 9 20 4 15 26 10 21 5 16 27 11 22 6 17)
>
Whoops! But where did that RECIPROCAL/MOD function come from?
That is, how do we find the multiplicative inverse of an integer
modulo another integer? After some helpful sidebar discussions
with Kenny, and rummaging around in Knuth's & Schneier's books,
it hit me. (D'Oh!) "Use the Web, Luke!":
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
This gives two methods, the extended Euclidean algorithm and
direct modular exponentiation using Euler's totient function.
Since the latter is a bit messy, let's look at the former:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
The simplest[1] version of this to code in Lisp is the recursive
method, which we can directly transliterate from the pseudocode
in the article like this:
> (defun extended-gcd (a b)
(if (zerop (mod a b))
(values 0 1)
(multiple-value-bind (x y)
(extended-gcd b (mod a b))
(values y (- x (* y (floor a b)))))))
EXTENDED-GCD
> (extended-gcd 3 17)
6
-1
> (extended-gcd 5 27)
11
-2
>
The primary value in each case is the desired reciprocol, that is,
3^-1 (mod 17) = 6, and 5^-1 (mod 27) = 11. Now all we need is a
simple wrapper that verifies that the LENGTH and STRIDE are co-prime:
> (defun reciprocal/mod (r n)
(multiple-value-bind (x y)
(extended-gcd r n)
(let ((gcd (+ (* r x) (* n y))))
(assert (= 1 gcd) () "~s and ~s are not co-prime!" r n)
(if (minusp x)
(+ x n) ; not necessary, but esthetically pleasing
x))))
RECIPROCAL/MOD
> (reciprocal/mod 3 17)
6
> (reciprocal/mod 5 27)
11
> (reciprocal/mod 9 27)
Error in function LISP::ASSERT-ERROR: 9 and 27 are not co-prime!
[Condition of type SIMPLE-ERROR]
...
With those two helpful functions, IOTA/MOD/STRIDE will work as shown.
QED.
[Note that in CMUCL, when all the above functions are compiled,
no bytes are consed for R, N less than ~10000, and only 48 bytes
[due to the "(+ (* r x) (* n y)" term in RECIPROCAL/MOD] for
R, N that are large fixnums. So the above will definitely cons
less than the temporary array version.]
-Rob
[1] I said, "The simplest method in Lisp is the recursive method",
but the iterative method might be faster. Exercise for the reader:
Recode EXTENDED-GCD using the iterative method and compare with
the recursive method for execution time & bytes consed.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Oh, and Mr. Warnock - thank you also for the wonderfully informative
reply. I was going back through the discussion to make sure Iw as
understanding everything - and noticed I missed your second reply the
first time through.
From: Kalle Olavi Niemitalo
Subject: Re: SETF and variable issues in Self Similar program.
Date:
Message-ID: <87tzmvfmv7.fsf@Astalo.kon.iki.fi>
Eric <·············@gmail.com> writes:
> The one problem that I am running into is a problem with setf.
> Because any number of ratios may be input, I am automatically creating
> variables and assigning names to them. I am doing it like this...
>
> (setf (car (symbol-bundle 2 (list 'listx *counta*))) whatever)
This expression calls SYMBOL-BUNDLE with the specified arguments
and writes the value of WHATEVER to the car of the returned cons cell.
So if SYMBOL-BUNDLE returns e.g. a list (listx1 listx2), and WHATEVER
is 4, then this changes the list to (4 listx2). It does not access
the LISTX1 variable at all.
It's the same thing as here:
(defparameter *some* '*other*)
(defparameter *other* nil)
(setf *some* t)
Even though the value of *SOME* is the name of another variable *OTHER*,
the SETF form changes only the *SOME* variable, rather than the *OTHER*
variable. So after the SETF, the value of *SOME* is T, and the value
of *OTHER* is still NIL.
If you want to modify the value of a variable whose name you get
from an expression, you can do it like this:
(setf (symbol-value (car (symbol-bundle 2 (list 'listx *counta*)))) whatever)
> Also - are there simple ways of automatically creating incremented
> variable names? I tried intern on strings but that didn't work too
> well, and settled on my current method.
There are also GENSYM and GENTEMP. However, instead of creating
multiple variables like that, you might consider using an array.
> If you want to modify the value of a variable whose name you get
> from an expression, you can do it like this:
>
> (setf (symbol-value (car (symbol-bundle 2 (list 'listx *counta*)))) whatever)
I thought I had the problem fixed, but it just popped up later in the
code once again with append,
and using symbol-value did the trick. I am suprised that the text I
read didn't mention these
types of things. Or maybe I just didn't get to that part yet.
Well, I will definitely be using symbol-value quite often in the
future.
> There are also GENSYM and GENTEMP. However, instead of creating
> multiple variables like that, you might consider using an array.
I'll look into them, thank you.