Hi all.
[BACKGROUND]
It's not a homework, just hacking around ;)
I hope I'll understand better all that Gauss method
if I implement it ....
[DETAILS]
Lisp-1 implementation: librep
Code supposed to do: exchange 2 rows in a matrix
Matrix representation: list of rows (each row being
a list of numbers)
The code:
####
(define (xchg-rows m r1 r2) ; (almost?) tail recursive
(letrec ((kern (lambda (m r1 r2 done r1-replacement r2-replacement)
(cond
((null m)
done)
((= r1 0)
(kern
(cdr m) (- r1 1) (- r2 1)
(cons r1-replacement done) r1-replacement r2-replacement))
((= r2 0)
(kern
(cdr m) (- r1 1) (- r2 1)
(cons r2-replacement done) r1-replacement r2-replacement))
(t
(kern
(cdr m) (- r1 1) (- r2 1)
(cons (car m) done) r1-replacement r2-replacement))))))
(reverse (kern m r1 r2 '() (nth r2 m) (nth r1 m)))))
####
[QUESTIONS]
1. Besides style, any reason that (reverse ..) should go
inside kern->cond->null m ?
2. How can that be simplified ?
Thanks in advance.
Wade Humeniuk wrote:
> ilya wrote:
>
>> [QUESTIONS]
>> 1. Besides style, any reason that (reverse ..) should go
>> inside kern->cond->null m ?
>> 2. How can that be simplified ?
>>
>> Thanks in advance.
>
>
> Use CL
Yep, that would be easier
but librep was chosen for a reason ;)
>
> (defun xchg-rows (matrix n m) (rotatef (nth n matrix) (nth m matrix)))
Thanks.
[example snipped]
> Wade
Anyway I'm learning CL too so here is my next q. :
And if I want pure functional solution [ say using CL ;) ] ?
On Tue, 13 Apr 2004 09:03:21 +0300, Ilya Sher <············@example.com> wrote:
> Wade Humeniuk wrote:
>
>> (defun xchg-rows (matrix n m)
>> (rotatef (nth n matrix) (nth m
>> matrix)))
>
> And if I want pure functional solution [ say using CL ;) ] ?
(defun copy-matrix (matrix)
(mapcar #'copy-list matrix))
(defun xchg-rows* (matrix n m)
(xchg-rows (copy-matrix matrix) n m))
Edi.
Edi Weitz wrote:
> On Tue, 13 Apr 2004 09:03:21 +0300, Ilya Sher <············@example.com> wrote:
>
>
>>Wade Humeniuk wrote:
>>
>>
>>>(defun xchg-rows (matrix n m)
>>> (rotatef (nth n matrix) (nth m
>>> matrix)))
>>
>>And if I want pure functional solution [ say using CL ;) ] ?
>
>
> (defun copy-matrix (matrix)
> (mapcar #'copy-list matrix))
>
> (defun xchg-rows* (matrix n m)
> (xchg-rows (copy-matrix matrix) n m))
>
> Edi.
>
Hmm...
I meant "pure functional to the core" ;) ...
without using any setters.
On Tue, 13 Apr 2004 11:55:12 +0300, Ilya Sher <············@example.com> wrote:
> I meant "pure functional to the core" ;) ...
> without using any setters.
Why?
Edi Weitz wrote:
> On Tue, 13 Apr 2004 11:55:12 +0300, Ilya Sher <············@example.com> wrote:
>
>
>>I meant "pure functional to the core" ;) ...
>>without using any setters.
>
>
> Why?
Because I'm learning.
I would like to see "pure" code for now.
Yes, even if it conses too much and therefore
eats CPU and memory.
Ilya Sher <············@example.com> writes:
> Edi Weitz wrote:
> > On Tue, 13 Apr 2004 11:55:12 +0300, Ilya Sher <············@example.com> wrote:
> >
>
> >>I meant "pure functional to the core" ;) ...
> >>without using any setters.
> > Why?
>
>
> Because I'm learning.
> I would like to see "pure" code for now.
Why? What is it about "purity" that is such a goal for you?
Did someone tell you that "purity" or "pure functional" is
the Right Way to program?
> Yes, even if it conses too much and therefore
> eats CPU and memory.
Heh :-)
--
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
Duane Rettig wrote:
[snip]
>>Because I'm learning.
>>I would like to see "pure" code for now.
>
>
> Why? What is it about "purity" that is such a goal for you?
> Did someone tell you that "purity" or "pure functional" is
> the Right Way to program?
I can always start producing "dirty" code.
As for now I want to learn in-depth the "pure" style.
I can produce "dirty" in many languages.
In some of them it's much simplier than "pure".
I can _only_ produce "dirty" in some.
Lisp is the opportunity ;)
And there is some other reason that I don't
yet know ;) I did not had yet the "calculus"
course (or how that it's called?) ;)
>
>
>>Yes, even if it conses too much and therefore
>>eats CPU and memory.
>
>
> Heh :-)
>
Ilya Sher <············@example.com> writes:
> Duane Rettig wrote:
> [snip]
> >>Because I'm learning.
> >>I would like to see "pure" code for now.
> > Why? What is it about "purity" that is such a goal for you?
>
> > Did someone tell you that "purity" or "pure functional" is
> > the Right Way to program?
>
> I can always start producing "dirty" code.
> As for now I want to learn in-depth the "pure" style.
You're assuming (or perhaps you've heard somewhere) that there is
a "dirty" style and a "pure" style. There isn't. Every style
has purity and dirtiness within it. It only varies by degree
and goal. I'm trying to get you to tell me what kind of purity
you're looking for.
> I can produce "dirty" in many languages.
You can produce dirty in every language.
> In some of them it's much simplier than "pure".
> I can _only_ produce "dirty" in some.
> Lisp is the opportunity ;)
>
> And there is some other reason that I don't
> yet know ;) I did not had yet the "calculus"
> course (or how that it's called?) ;)
Ah, the lambda calculus? Purely functional? What?
--
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
Duane Rettig <·····@franz.com> writes:
> Ilya Sher <············@example.com> writes:
>> I can always start producing "dirty" code.
>> As for now I want to learn in-depth the "pure" style.
>
> You're assuming (or perhaps you've heard somewhere) that there is
> a "dirty" style and a "pure" style. There isn't.
There is a style known as `pure functional'.
Joe Marshall <···@ccs.neu.edu> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Ilya Sher <············@example.com> writes:
>
> >> I can always start producing "dirty" code.
> >> As for now I want to learn in-depth the "pure" style.
> >
> > You're assuming (or perhaps you've heard somewhere) that there is
> > a "dirty" style and a "pure" style. There isn't.
>
> There is a style known as `pure functional'.
Of course. But it looks like the poster has no idea what it is,
and is just spouting words that were heard somewhere.
I know someone else joked about my attempt to get into the mind
of this person, but it was truly an honest attempt to help. Whenever
I try to help someone gain some understanding, I find that it wastes
much less time to find out where the person is coming from, and to
take it from there, than to just make assumptions and then have to
backtrack because those assumptions were wrong. It is now clear
that in this forum at least, this person is not interested in
revealing the bases for these questions, and for this reason I
cannot be of help.
--
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
Duane Rettig wrote:
> Joe Marshall <···@ccs.neu.edu> writes:
>
>
>>Duane Rettig <·····@franz.com> writes:
>>
>>
>>>Ilya Sher <············@example.com> writes:
>>
>>>>I can always start producing "dirty" code.
>>>>As for now I want to learn in-depth the "pure" style.
>>>
>>>You're assuming (or perhaps you've heard somewhere) that there is
>>>a "dirty" style and a "pure" style. There isn't.
>>
>>There is a style known as `pure functional'.
>
>
> Of course. But it looks like the poster has no idea what it is,
> and is just spouting words that were heard somewhere.
I know in general.
I would summ it up as (correct if wrong):
A function have no side effects and returns
always the same results for same input.
It have many positive consequeneces which I don't really know
in depth but one of them is that you can cache results (assuming
it worth (cpu cycles saved) and is bearable (not consuming too
much memory))
Any additional links to reading about this issue
(electronic format,not books) will be helpful.
>
> I know someone else joked about my attempt to get into the mind
> of this person, but it was truly an honest attempt to help. Whenever
> I try to help someone gain some understanding, I find that it wastes
> much less time to find out where the person is coming from, and to
> take it from there, than to just make assumptions and then have to
> backtrack because those assumptions were wrong. It is now clear
> that in this forum at least, this person is not interested in
> revealing the bases for these questions, and for this reason I
> cannot be of help.
>
Sorry for wrong impression.
I'm just seeking something like "perfect code" for
the problem. I want to learn by examples of really
good code. Sorry, what I think it is.
Ilya Sher <············@example.com> writes:
> Duane Rettig wrote:
> > Joe Marshall <···@ccs.neu.edu> writes:
> >
>
> >>Duane Rettig <·····@franz.com> writes:
> >>
> >>
> >>>Ilya Sher <············@example.com> writes:
> >>
> >>>>I can always start producing "dirty" code.
> >>>>As for now I want to learn in-depth the "pure" style.
> >>>
> >>>You're assuming (or perhaps you've heard somewhere) that there is
> >>> a "dirty" style and a "pure" style. There isn't.
>
> >>
> >>There is a style known as `pure functional'.
> > Of course. But it looks like the poster has no idea what it is,
>
> > and is just spouting words that were heard somewhere.
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
OK, this does help me to understand where you're coming from.
One other requirement for a pure-function is that it be a solution
for a purely functional problem. See below for more on this.
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
> > I know someone else joked about my attempt to get into the mind
> > of this person, but it was truly an honest attempt to help. Whenever
> > I try to help someone gain some understanding, I find that it wastes
> > much less time to find out where the person is coming from, and to
> > take it from there, than to just make assumptions and then have to
> > backtrack because those assumptions were wrong. It is now clear
> > that in this forum at least, this person is not interested in
> > revealing the bases for these questions, and for this reason I
> > cannot be of help.
> >
>
> Sorry for wrong impression.
> I'm just seeking something like "perfect code" for
> the problem. I want to learn by examples of really
> good code. Sorry, what I think it is.
The perfect code for a problem is the code that solves the
problem. In this case I mean "perfect" as in "complete" or
"being or performing as intended", and not as "without blemish".
In your original request, you wanted a way to exchange rows in a
matrix. But in this article you added that you preferred to do
this without consuming too much memory. My contention is that
this is not the right problem for a functional solution, because
a purely functional solution will necessarily cons a new matrix
at least the first time for each set of arguments, and if the
function is not memoized it will cons for every invocation. If
you disturb the original matrix, that's a side-effect, and thus
not purely functional (it has the dual spoiler of pure-functional
of not being side-effect free and also not being repeatable,
though if it is the same two rows that are being swapped I
suppose you could say that it is cyclic :-).
Whether or not you desire a pure-functional solution really
depends on your requiremnents. Many programmers start out by
saying "I don't care about consing" or "I don't care about
speed", but in the end the requirement is very much there; it
usually turns out to be a question of degree. A little consing
and/or slowness is tolerable for the sake of purity, especially if
that purity translates into better maintainability of the code,
but if it becomes so slow as to make you wonder why you did the
solution in this particular language, you will either switch
languages or care more about speed or consing the next time around.
--
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
Duane Rettig wrote:
[snip]
>
> The perfect code for a problem is the code that solves the
> problem. In this case I mean "perfect" as in "complete" or
> "being or performing as intended", and not as "without blemish".
>
> In your original request, you wanted a way to exchange rows in a
> matrix.
> But in this article you added that you preferred to do
> this without consuming too much memory.
Maybe I was not clear enough. I asked for functional solution
despite this fact:
####
I would like to see "pure" code for now.
Yes, even if it conses too much and therefore
eats CPU and memory.
####
> My contention is that
> this is not the right problem for a functional solution, because
> a purely functional solution will necessarily cons a new matrix
> at least the first time for each set of arguments, and if the
> function is not memoized it will cons for every invocation. If
> you disturb the original matrix, that's a side-effect, and thus
> not purely functional (it has the dual spoiler of pure-functional
> of not being side-effect free and also not being repeatable,
> though if it is the same two rows that are being swapped I
> suppose you could say that it is cyclic :-).
>
> Whether or not you desire a pure-functional solution really
> depends on your requiremnents.
Agreed but I don't have real-life requirements at
this stage of learning.
> Many programmers start out by
> saying "I don't care about consing" or "I don't care about
> speed", but in the end the requirement is very much there; it
> usually turns out to be a question of degree.
Agreed.
> A little consing
> and/or slowness is tolerable for the sake of purity, especially if
> that purity translates into better maintainability of the code,
> but if it becomes so slow as to make you wonder why you did the
> solution in this particular language, you will either switch
> languages or care more about speed or consing the next time around.
>
Ilya Sher <············@example.com> writes:
> Duane Rettig wrote:
> [snip]
> >
> > The perfect code for a problem is the code that solves the
> > problem. In this case I mean "perfect" as in "complete" or
> > "being or performing as intended", and not as "without blemish".
> >
> > In your original request, you wanted a way to exchange rows in a
> > matrix.
>
> > But in this article you added that you preferred to do
> > this without consuming too much memory.
>
> Maybe I was not clear enough. I asked for functional solution
> despite this fact:
> ####
> I would like to see "pure" code for now.
> Yes, even if it conses too much and therefore
> eats CPU and memory.
> ####
Butting in here because I'm avoiding work and silly things like this
can be fun on occasion... how about this:
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt
(worker (cdr list) (1- x) (1- y) x-elt)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
At worst it traverses the list twice, and only uses stack space linear
to the length of the list. Stack space is just memory, after all.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas F. Burdick wrote:
> Ilya Sher <············@example.com> writes:
>
>
>>Duane Rettig wrote:
>>[snip]
>>
>>>The perfect code for a problem is the code that solves the
>>>problem. In this case I mean "perfect" as in "complete" or
>>>"being or performing as intended", and not as "without blemish".
>>>
>>>In your original request, you wanted a way to exchange rows in a
>>>matrix.
>>
>>>But in this article you added that you preferred to do
>>>this without consuming too much memory.
>>
>>Maybe I was not clear enough. I asked for functional solution
>>despite this fact:
>>####
>>I would like to see "pure" code for now.
>>Yes, even if it conses too much and therefore
>>eats CPU and memory.
>>####
>
>
> Butting in here because I'm avoiding work and silly things like this
> can be fun on occasion... how about this:
>
> (defun swap-elements (list x y)
> (labels ((worker (list x y x-elt)
> (cond
> ((null list) nil)
> ((zerop x) (cons (nth y list)
> (worker (cdr list) (1- x) (1- y) (car list))))
> ((zerop y) (cons x-elt
> (worker (cdr list) (1- x) (1- y) x-elt)))
> (t (cons (car list)
> (worker (cdr list) (1- x) (1- y) x-elt))))))
> (if (<= x y)
> (worker list x y nil)
> (worker list y x nil))))
>
> At worst it traverses the list twice, and only uses stack space linear
> to the length of the list. Stack space is just memory, after all.
>
Seems nice.
Thanks.
Patch ;)
((zerop y) (cons x-elt
- (worker (cdr list) (1- x) (1- y) x-elt)))
+ (worker (cdr list) (1- x) (1- y) nil)))
Will save memory I guess (not that I care but passing
something that won't be used ...)
Ilya Sher <············@example.com> writes:
> ((zerop y) (cons x-elt
> - (worker (cdr list) (1- x) (1- y) x-elt)))
> + (worker (cdr list) (1- x) (1- y) nil)))
>
> Will save memory I guess (not that I care but passing
> something that won't be used ...)
Nope, you're still passing a lisp object on the stack. Although, now
that you mention it, the recursion should stop there, since it doesn't
need to copy the rest of the list:
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt (cdr list)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
The worst case is still the same, but now the best case is significantly better.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas F. Burdick butted in
> silly things like this
> can be fun on occasion...
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt
(worker (cdr list) (1- x) (1- y) x-elt)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
> At worst it traverses the list twice,...
That is beautiful code. It has a sparkling, gem like
quality.
I've laboured to eliminate the duplicate list traversal
implicit in the use of nth, and have come up with this ugly
beasty, that processes on both the flood and the ebb of the
recursion.
(defun swap-elements (list first-index second-index)
(labels ((worker (list first-index second-index carry-down)
(if (zerop second-index)
(values (cons carry-down (cdr list))
(car list))
(multiple-value-bind (ascending-list carry-up)
(worker (cdr list)
(- first-index 1)
(- second-index 1)
(if (zerop first-index)
(car list)
carry-down))
(if (zerop first-index)
(cons carry-up ascending-list)
(values (cons (car list) ascending-list)
carry-up))))))
(if (<= first-index second-index)
(worker list first-index second-index nil)
(worker list second-index first-index nil))))
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> Thomas F. Burdick butted in
>
>>silly things like this
>>can be fun on occasion...
>
>
> (defun swap-elements (list x y)
> (labels ((worker (list x y x-elt)
> (cond
> ((null list) nil)
> ((zerop x) (cons (nth y list)
> (worker (cdr list) (1- x) (1- y) (car list))))
> ((zerop y) (cons x-elt
> (worker (cdr list) (1- x) (1- y) x-elt)))
> (t (cons (car list)
> (worker (cdr list) (1- x) (1- y) x-elt))))))
> (if (<= x y)
> (worker list x y nil)
> (worker list y x nil))))
>
>
>>At worst it traverses the list twice,...
>
>
> That is beautiful code. It has a sparkling, gem like
> quality.
That is what I was looking for ;)
>
> I've laboured to eliminate the duplicate list traversal
> implicit in the use of nth, and have come up with this ugly
> beasty, that processes on both the flood and the ebb of the
> recursion.
>
> (defun swap-elements (list first-index second-index)
> (labels ((worker (list first-index second-index carry-down)
> (if (zerop second-index)
> (values (cons carry-down (cdr list))
> (car list))
> (multiple-value-bind (ascending-list carry-up)
> (worker (cdr list)
> (- first-index 1)
> (- second-index 1)
> (if (zerop first-index)
> (car list)
> carry-down))
> (if (zerop first-index)
> (cons carry-up ascending-list)
> (values (cons (car list) ascending-list)
> carry-up))))))
> (if (<= first-index second-index)
> (worker list first-index second-index nil)
> (worker list second-index first-index nil))))
>
> Alan Crowe
> Edinburgh
> Scotland
>
>
Looks complicated :(
Ilya Sher <············@example.com> writes:
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
The primary advantage of pure functions is that they compose nicely.
Greetings! Just wondering if it is possible to have a lisp compiler
setting triggering warning or failure for non-functional code. Also
wondering whether this has already been achieved anywhere.
Take care,
Joe Marshall <···@ccs.neu.edu> writes:
> Ilya Sher <············@example.com> writes:
>
> > I know in general.
> > I would summ it up as (correct if wrong):
> >
> > A function have no side effects and returns
> > always the same results for same input.
> > It have many positive consequeneces which I don't really know
> > in depth but one of them is that you can cache results (assuming
> > it worth (cpu cycles saved) and is bearable (not consuming too
> > much memory))
>
> The primary advantage of pure functions is that they compose nicely.
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
Camm Maguire <····@enhanced.com> writes:
> Greetings! Just wondering if it is possible to have a lisp compiler
> setting triggering warning or failure for non-functional code. Also
> wondering whether this has already been achieved anywhere.
Are you talking about "unreachable code" or "dead code"? Or are you
talking about something else?
I've seen some sort of dead code removal message from the SBCL
compiler, but it didn't mention what that code was. At least I think
I did.
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
On Wed, 14 Apr 2004 22:50:41 -0400, David Steuber wrote:
> Camm Maguire <····@enhanced.com> writes:
>
>> Greetings! Just wondering if it is possible to have a lisp compiler
>> setting triggering warning or failure for non-functional code. Also
>> wondering whether this has already been achieved anywhere.
>
> Are you talking about "unreachable code" or "dead code"? Or are you
> talking about something else?
>
> I've seen some sort of dead code removal message from the SBCL
> compiler, but it didn't mention what that code was. At least I think
> I did.
I think the OP was talking about detection of code with side-effects.
It should be very easy to do: Have a list of primitives that have
side effects, and then to check if a given function has side effects
you just recursively check each function that it calls, until either
you find a primitive with side effects, or you exhaust the tree and
have proved that the function has no side effects.
Having said it's easy, I've never seen it implemented in any Lisp
I've used so maybe there are hidden details (or maybe they're not
so hidden and I'm just wrong).
Cheers,
Bill.
--
Dr. William Bland www.abstractnonsense.com
Computer Programmer awksedgrep (Yahoo IM)
Any sufficiently advanced Emacs user is indistinguishable from magic
Greetings!
William Bland <····@abstractnonsense.com> writes:
> On Wed, 14 Apr 2004 22:50:41 -0400, David Steuber wrote:
>
> > Camm Maguire <····@enhanced.com> writes:
> >
> >> Greetings! Just wondering if it is possible to have a lisp compiler
> >> setting triggering warning or failure for non-functional code. Also
> >> wondering whether this has already been achieved anywhere.
> >
> > Are you talking about "unreachable code" or "dead code"? Or are you
> > talking about something else?
> >
> > I've seen some sort of dead code removal message from the SBCL
> > compiler, but it didn't mention what that code was. At least I think
> > I did.
>
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
>
Yes, and this is what I was thinking of as a solution too. Would
appear helpful in determining thread safe code. GCL has some
rudimentary ability to make use of side-effect info in optimizing
functions, but doesn't calculate this info to my understanding.
Take care,
> Having said it's easy, I've never seen it implemented in any Lisp
> I've used so maybe there are hidden details (or maybe they're not
> so hidden and I'm just wrong).
>
> Cheers,
> Bill.
> --
> Dr. William Bland www.abstractnonsense.com
> Computer Programmer awksedgrep (Yahoo IM)
> Any sufficiently advanced Emacs user is indistinguishable from magic
>
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
In article <······························@abstractnonsense.com>,
William Bland <····@abstractnonsense.com> wrote:
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
Except that doesn't really tell you what you want to know. It's much
more important that things have pure functional interfaces than that
they have pure functional implementations. A good compiler for a pure
functional language will turn lots of your mutation-free code into code
that uses mutation under the hood. With not such a good compiler, you
can do it yourself.
There's nothing at all wrong with consing up a list in the "wrong" order
and then calling nreverse on it before returning it. The interface is
pure functional, even though the implementation isn't.
-- Bruce
* William Bland wrote:
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
It's not easy to do. Consider something like this:
(defun grovel-list (fun l &optional (comparator nil comparatorp))
(loop for e in l
when (funcall fun e) collect e into results
finally (return (if comparatorp
(sort results comparator)
results))))
This is a side-effect-free function, but its implementation has one
explicit call to a non-side-effect-free function (SORT) and the
expansion of LOOP is probably a mass of side-effects.
--tim
On Sat, 17 Apr 2004 19:35:15 +0100, Tim Bradshaw wrote:
> * William Bland wrote:
>
>> I think the OP was talking about detection of code with side-effects.
>> It should be very easy to do: Have a list of primitives that have
>> side effects, and then to check if a given function has side effects
>> you just recursively check each function that it calls, until either
>> you find a primitive with side effects, or you exhaust the tree and
>> have proved that the function has no side effects.
>
> It's not easy to do. Consider something like this:
>
> (defun grovel-list (fun l &optional (comparator nil comparatorp))
> (loop for e in l
> when (funcall fun e) collect e into results
> finally (return (if comparatorp
> (sort results comparator)
> results))))
>
> This is a side-effect-free function, but its implementation has one
> explicit call to a non-side-effect-free function (SORT) and the
> expansion of LOOP is probably a mass of side-effects.
>
> --tim
Ah, I see, thanks for pointing this out - I should have thought
about it a bit harder. I suppose to do this properly then, you
would need a fairly sophisticated approach using an automated
theorem prover or something. It probably wouldn't be worth the
effort.
Cheers,
Bill.
--
Dr. William Bland www.abstractnonsense.com
Computer Programmer awksedgrep (Yahoo IM)
Any sufficiently advanced Emacs user is indistinguishable from magic
Ilya Sher wrote:
> Duane Rettig wrote:
>
>> Joe Marshall <···@ccs.neu.edu> writes:
>>
>>
>>> Duane Rettig <·····@franz.com> writes:
>>>
>>>
>>>> Ilya Sher <············@example.com> writes:
>>>
>>>
>>>>> I can always start producing "dirty" code.
>>>>> As for now I want to learn in-depth the "pure" style.
>>>>
>>>>
>>>> You're assuming (or perhaps you've heard somewhere) that there is
>>>> a "dirty" style and a "pure" style. There isn't.
>>>
>>>
>>> There is a style known as `pure functional'.
>>
>>
>>
>> Of course. But it looks like the poster has no idea what it is,
>> and is just spouting words that were heard somewhere.
>
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
>
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
>
>>
>> I know someone else joked about my attempt to get into the mind
>> of this person, but it was truly an honest attempt to help. Whenever
>> I try to help someone gain some understanding, I find that it wastes
>> much less time to find out where the person is coming from, and to
>> take it from there, than to just make assumptions and then have to
>> backtrack because those assumptions were wrong. It is now clear
>> that in this forum at least, this person is not interested in
>> revealing the bases for these questions, and for this reason I
>> cannot be of help.
>>
> Sorry for wrong impression.
> I'm just seeking something like "perfect code" for
> the problem. I want to learn by examples of really
> good code. Sorry, what I think it is.
A few places to start reading about pure-functional programming are:
http://www.md.chalmers.se/~rjmh/Papers/whyfp.html
http://www.haskell.org/
http://www.cs.oberlin.edu/classes/dragn/labs/combinators/combinators.html
Folks have raised some valid questions about whether anyone should care
about pure functional programming. The best reply I know of is that pure
functional programming is fun, an interesting intellectual exercise, a
fun problem. As well, some stuff that comes out of trying to do it is
beautiful. I think the thing that makes me like pure-functional
languages and associated stuff is approximately the same thing that made
me like abstract algebras when I was in college.
Also, one can admire the long distance that pure-functional folks have
come in compiler development in roughly the same way one can admire the
very clever developments that Lisp compiler writers have made over the
years in order to get Lisp compilers that compete well with languages
like C. The best functional-language compilers produce results that are
pretty close to the best Lisp or C compilers, a result that is
impressive, considering how much slower naive implementations of
pure-functional languages are even than naive implementations of Lisp.
mikel wrote:
> http://www.md.chalmers.se/~rjmh/Papers/whyfp.html
"Why Functional Programming Matters"
I'm reading this one. I even recommend it to all who asked
"why?" ;)
> http://www.haskell.org/
> http://www.cs.oberlin.edu/classes/dragn/labs/combinators/combinators.html
Will read thise later.
Thanks for the links.
[snip]
On Wed, 14 Apr 2004 20:48:36 +0300, Ilya Sher wrote:
> Duane Rettig wrote:
>
> A function have no side effects and returns
> always the same results for same input.
That is exactly what most "dirty" examples showed to you here do.
For example the one by Edi Weitz:
(defun copy-matrix (matrix)
(mapcar #'copy-list matrix))
(defun xchg-rows* (matrix n m)
(xchg-rows (copy-matrix matrix) n m))
It will return a copy of the original matrix that has the rows exchanged.
Just like a purely functional solution would construct such a matrix by
recursing over the original one.
Why does it matter how the result is constructed as long as the behavior
of the function is still "functional"?
On Wed, 14 Apr 2004 19:24:04 +0200, Simon Adameit wrote:
>> Duane Rettig wrote:
>> [snip]
I'm sorry for wrong quoting. It was of course Ilya Sher who wrote that.
Simon Adameit wrote:
> Why does it matter how the result is constructed as long as the behavior
> of the function is still "functional"?
Learning purposes.
Intellectual game.
Good feeling about the code.
Ilya Sher <············@example.com> writes:
> A function have no side effects and returns
> always the same results for same input.
How do you define "same"? Is (list 1 2) the same as (list 1 2)? (The
answer, in the normal way I've seen the word "same" used in the context
of Lisp, is "no", since the two lists are not EQ.)
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain <·····@nyct.net> writes:
> Ilya Sher <············@example.com> writes:
>
>> A function have no side effects and returns
>> always the same results for same input.
>
> How do you define "same"?
For a functional language, a reasonable definition of `same' is
`functionally equivalent'.
> Is (list 1 2) the same as (list 1 2)? (The answer, in the normal
> way I've seen the word "same" used in the context of Lisp, is "no",
> since the two lists are not EQ.)
The answer is `maybe'. They aren't EQ obviously, but they are EQUAL.
If you use eschew side effects, then EQUAL should be a sufficient
comparison.
Ilya Sher <············@example.com> wrote in message news:<······················@lnews.actcom.co.il>...
> Duane Rettig wrote:
> > Joe Marshall <···@ccs.neu.edu> writes:
> >
> >
> >>Duane Rettig <·····@franz.com> writes:
> >>
> >>
> >>>Ilya Sher <············@example.com> writes:
>
> >>>>I can always start producing "dirty" code.
> >>>>As for now I want to learn in-depth the "pure" style.
> >>>
> >>>You're assuming (or perhaps you've heard somewhere) that there is
> >>>a "dirty" style and a "pure" style. There isn't.
> >>
> >>There is a style known as `pure functional'.
> >
> >
> > Of course. But it looks like the poster has no idea what it is,
> > and is just spouting words that were heard somewhere.
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
>
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
> >
Hi Ilya --
There's something called "the Leibniz principle": you use in
mathematics all the time: whenever you apply the same function to two
equivalent terms, the result is also equivalent; for instance:
x^2 = x*x
which you know to be true.
If you were to apply a function to both terms of this equivalence,
the result would also retain the equivalence relation between terms.
f(x^2) = f(x*x)
You know this from high school math.
When you program in imperative style, say
y:= f(x);
while b(y) do
y := g(y);
z := h(y)
it might be that attributing g(y) to y breaks the principle above
(for instance, through side effect in a subroutine called by g). It
becomes much harder to garantee the integrity of the equivalence
relation when you go back to the main loop (for example).
When you program in functional style you would change the code
snippet above (actually, you wouldn't even write it) to something that
relied upon induction. The correctness of the code could be proved
mathematically by induction. That particular "school" claims that it
is a better way to program, because you can prove correctness like you
prove a theorem (there are other approaches to "proving program
correctness as if they were theorems", like the "school" of
Hoare/Djikstra/Gries/etc.).
IMHO, the literature on ML (or Haskell there are more books on ML,
though). On Lisp touches on these issues in a deeper way than Ansi
Common Lisp (Paul Graham).
HTH
Cheers
Henry
Joe Marshall <···@ccs.neu.edu> writes:
> Duane Rettig <·····@franz.com> writes:
>
>> Ilya Sher <············@example.com> writes:
>
>>> I can always start producing "dirty" code.
>>> As for now I want to learn in-depth the "pure" style.
>>
>> You're assuming (or perhaps you've heard somewhere) that there is
>> a "dirty" style and a "pure" style. There isn't.
>
> There is a style known as `pure functional'.
but is there purely functional hardware?
--
I'm a Lisp variable -- bind me!
Michael Livshin wrote:
> Joe Marshall <···@ccs.neu.edu> writes:
>
>
>>Duane Rettig <·····@franz.com> writes:
>>
>>
>>>Ilya Sher <············@example.com> writes:
>>
>>>>I can always start producing "dirty" code.
>>>>As for now I want to learn in-depth the "pure" style.
>>>
>>>You're assuming (or perhaps you've heard somewhere) that there is
>>>a "dirty" style and a "pure" style. There isn't.
>>
>>There is a style known as `pure functional'.
>
>
> but is there purely functional hardware?
>
Wouldn't that require infinite memory?
Hmm... how do we implement PC (program counter)
that is not overwritten on "inc" command ?
On Wed, 14 Apr 2004 19:33:14 +0300, Ilya Sher <············@example.com>
wrote:
> Michael Livshin wrote:
>> Joe Marshall <···@ccs.neu.edu> writes:
>>
>>
>>> Duane Rettig <·····@franz.com> writes:
>>>
>>>
>>>> Ilya Sher <············@example.com> writes:
>>>
>>>>> I can always start producing "dirty" code.
>>>>> As for now I want to learn in-depth the "pure" style.
>>>>
>>>> You're assuming (or perhaps you've heard somewhere) that there is
>>>> a "dirty" style and a "pure" style. There isn't.
>>>
>>> There is a style known as `pure functional'.
>>
>>
>> but is there purely functional hardware?
>>
> Wouldn't that require infinite memory?
> Hmm... how do we implement PC (program counter)
> that is not overwritten on "inc" command ?
You seem to misundestand.
All algebra on integers is done modulo some max number.
(Bignum confuses the issue.)
But the fact that all numbers are representated a mod b
does not determine wether it is functional or not.
Pure functional algorithms have the big advantage that
they are easy to reason over. (Mathematically)
It allows a tecnique called proof by generator induction.
In particluar it is much easier to see the loop invariants in a
recursive definition. It helps to have tried to proove algorithms
mathematically to fully appiciate the difference.
(Procedural programming can be handled by Hoare logic.)
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
John Thingstad wrote:
> On Wed, 14 Apr 2004 19:33:14 +0300, Ilya Sher <············@example.com>
> wrote:
>
>> Michael Livshin wrote:
>>
>>> Joe Marshall <···@ccs.neu.edu> writes:
>>>
>>>
>>>> Duane Rettig <·····@franz.com> writes:
>>>>
>>>>
>>>>> Ilya Sher <············@example.com> writes:
>>>>
>>>>
>>>>>> I can always start producing "dirty" code.
>>>>>> As for now I want to learn in-depth the "pure" style.
>>>>>
>>>>>
>>>>> You're assuming (or perhaps you've heard somewhere) that there is
>>>>> a "dirty" style and a "pure" style. There isn't.
>>>>
>>>>
>>>> There is a style known as `pure functional'.
>>>
>>>
>>>
>>> but is there purely functional hardware?
>>>
>> Wouldn't that require infinite memory?
>> Hmm... how do we implement PC (program counter)
>> that is not overwritten on "inc" command ?
>
>
> You seem to misundestand.
> All algebra on integers is done modulo some max number.
> (Bignum confuses the issue.)
I was thinking about all the consing here, not math.
> But the fact that all numbers are representated a mod b
> does not determine wether it is functional or not.
> Pure functional algorithms have the big advantage that
> they are easy to reason over. (Mathematically)
> It allows a tecnique called proof by generator induction.
Added to "to_learn". ;)
> In particluar it is much easier to see the loop invariants in a
> recursive definition. It helps to have tried to proove algorithms
> mathematically to fully appiciate the difference.
> (Procedural programming can be handled by Hoare logic.)
On 8713 day of my life Duane Rettig wrote:
> Ilya Sher <············@example.com> writes:
>>>> I meant "pure functional to the core" ;) ...
>>>> without using any setters.
>>> Why?
>> Because I'm learning.
>> I would like to see "pure" code for now.
>
> Why? What is it about "purity" that is such a goal for you?
> Did someone tell you that "purity" or "pure functional" is
> the Right Way to program?
He need advise, not psychoanalyst :)
May be, it is not Right Way, but Fun Way :)
--
Ivan Boldyrev
Sorry my terrible English, my native language is Lisp!
Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
> On 8713 day of my life Duane Rettig wrote:
> > Ilya Sher <············@example.com> writes:
> >>>> I meant "pure functional to the core" ;) ...
> >>>> without using any setters.
> >>> Why?
> >> Because I'm learning.
> >> I would like to see "pure" code for now.
> >
> > Why? What is it about "purity" that is such a goal for you?
> > Did someone tell you that "purity" or "pure functional" is
> > the Right Way to program?
>
> He need advise, not psychoanalyst :)
A says to B: "Tell me how to get where I want to go."
B says to A: "Do you know where you want to go?"
C says: "He needs advice, not a psychoanalyst."
:-)
> May be, it is not Right Way, but Fun Way :)
I'm _always_ having Fun.
--
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
On Tue, 13 Apr 2004 12:10:57 +0300, Ilya Sher <············@example.com> wrote:
> Edi Weitz wrote:
>> Why?
>
> Because I'm learning.
OK, so write it yourself... :)
IIRC you already had a "purely functional" version for Scheme. Why
don't you just use LABELS instead of LETREC and call it a day?
Note that it's generally not a good idea to write a function like this
in CL because the ANSI standard makes no guarantees about tail-call
eliminations (although most implementations can do it if given proper
declarations). Search the c.l.l archives for endless discussions about
this topic and the corresponding nomenclature if you mind.
Edi.
Edi Weitz wrote:
> On Tue, 13 Apr 2004 12:10:57 +0300, Ilya Sher <············@example.com> wrote:
>
>
>>Edi Weitz wrote:
>>
>>>Why?
>>
>>Because I'm learning.
>
>
> OK, so write it yourself... :)
Already did ;)
>
> IIRC you already had a "purely functional" version for Scheme.
Correct. And was looking for simplification as I'm
not sure it is the best/shortest way
(constrained to "pure functional") to do it.
> Why
> don't you just use LABELS instead of LETREC and call it a day?
See above.
>
> Note that it's generally not a good idea to write a function like this
> in CL because the ANSI standard makes no guarantees about tail-call
> eliminations
Known fact. Anyway that's better to give a chance ;)
> (although most implementations can do it if given proper
> declarations). Search the c.l.l archives for endless discussions about
> this topic and the corresponding nomenclature if you mind.
>
> Edi.
Edi Weitz wrote:
> On Tue, 13 Apr 2004 12:11:52 +0200, Edi Weitz <···@agharta.de> wrote:
>
>
>> * (defun exchange-elements (list m n)
>> (let ((mth (nth m list))
>> (nth (nth n list)))
>> (mapcar (lambda (element)
>> (cond ((eq element mth) nth)
>> ((eq element nth) mth)
>> (t element)))
>> list)))
>
>
> Yeah, I know - this relies on the elements of LIST being pairwise
> distinct w.r.t. #'EQ. So...
>
> * (defun exchange-elements (list m n)
> (let ((i 0))
> (mapcar (lambda (element)
> (declare (ignore element))
> (prog1
> (nth (cond
> ((= i n) m)
> ((= i m) n)
> (t i))
> list)
> (incf i)))
> list)))
>
> EXCHANGE-ELEMENTS
> * (exchange-elements *matrix* 1 3)
>
> ((1 2 3) (10 11 12) (7 8 9) (4 5 6))
> * (exchange-elements *matrix* 2 0)
>
> ((7 8 9) (4 5 6) (1 2 3) (10 11 12))
> * *matrix*
>
> ((1 2 3) (4 5 6) (7 8 9) (10 11 12))
>
> Now you are going to argue that I is destructively modified... :(
>
> Edi.
Thanks for all the variants. I will look into them later,
probably tommorrow. As for book - no book ;) and collecting
with "loop" is 'pure' enough for me ;)
Edi Weitz wrote:
> On Tue, 13 Apr 2004 12:11:52 +0200, Edi Weitz <···@agharta.de> wrote:
>
>
>> * (defun exchange-elements (list m n)
>> (let ((mth (nth m list))
>> (nth (nth n list)))
>> (mapcar (lambda (element)
>> (cond ((eq element mth) nth)
>> ((eq element nth) mth)
>> (t element)))
>> list)))
>
>
> Yeah, I know - this relies on the elements of LIST being pairwise
> distinct w.r.t. #'EQ. So...
Yep,the first ver. would be _kind of_ ok for matrices rows
but not for general exchange 'cause you might have
list of numbers and they are so easy (eq)'ed ;)
>
> * (defun exchange-elements (list m n)
> (let ((i 0))
> (mapcar (lambda (element)
> (declare (ignore element))
> (prog1
> (nth (cond
> ((= i n) m)
> ((= i m) n)
> (t i))
> list)
> (incf i)))
> list)))
>
> EXCHANGE-ELEMENTS
> * (exchange-elements *matrix* 1 3)
>
> ((1 2 3) (10 11 12) (7 8 9) (4 5 6))
> * (exchange-elements *matrix* 2 0)
>
> ((7 8 9) (4 5 6) (1 2 3) (10 11 12))
> * *matrix*
>
> ((1 2 3) (4 5 6) (7 8 9) (10 11 12))
>
> Now you are going to argue that I is destructively modified... :(
Well, you already said that ;)
>
> Edi.
(nth ...) have interesting idea of chosing the index
with (cond ...)
I don't like (ignore ...) though (as you might guess) ;)
Thanks for interesting ideas.
On Wed, 14 Apr 2004 08:41:59 +0300, Ilya Sher <············@example.com> wrote:
> I don't like (ignore ...) though (as you might guess) ;)
Now what's your problem with that one?
Edi Weitz wrote:
> On Wed, 14 Apr 2004 08:41:59 +0300, Ilya Sher <············@example.com> wrote:
>
>
>>I don't like (ignore ...) though (as you might guess) ;)
>
>
> Now what's your problem with that one?
It "doesn't feel right" to me.
No logical explanation ("feel").
If you don't feel that way - forget it,
sorry for bothering you.
Ilya replied:
>> Why?
>
> Because I'm learning.
> I would like to see "pure" code for now.
> Yes, even if it conses too much and therefore
> eats CPU and memory.
;;; We have a matrix, rows 0,1,...
;;; We want to exchange rows i and j
;;; First we break it into five pieces
;;; rows 0 to i-1
;;; row i
;;; row i+1 to j-1
;;; row j
;;; row j+1 ...
;;; Then we put it back together
;;; So we start with a utility function to break off the first n rows
(defun break-off-first-n-rows(n remaining-rows broken-off-already)
(if (zerop n)(list remaining-rows broken-off-already)
(break-off-first-n-rows (- n 1)
(cdr remaining-rows)
(cons (car remaining-rows)
broken-off-already))))
(defun break-up (matrix i j)
(let ((first-break
(break-off-first-n-rows i matrix '())))
(let ((row-i (caar first-break))
(row-i+1-up (cdar first-break)))
(let ((second-break
(break-off-first-n-rows (- j (+ i 1))
row-i+1-up
'())))
(let ((mid-section (cadr second-break))
(row-j (caar second-break))
(remainder (cdar second-break)))
(rebuild (cadr first-break)
(cons row-j
(rebuild mid-section
(cons row-i
remainder)))))))))
(defun rebuild (broken-off-bit already-rebuilt)
(if broken-off-bit
(rebuild (cdr broken-off-bit)
(cons (car broken-off-bit)
already-rebuilt))
already-rebuilt))
(break-up '(0 1 2 3 4 5 6 7 8 9) 3 6)
=> (0 1 2 6 4 5 3 7 8 9)
* (break-up '((0.0 0.1)(1.0 1.1)) 0 1)
=> ((1.0 1.1) (0.0 0.1))
Exchange columns by transposing the matrix, exchanging the
rows, transposing the matrix.
I much prefer to call this Traditional New Orleans Style
Lisp, like they wrote in the 1920's. I distrust the practise
of calling this style "pure functional programming", it
reminds me too much of Adolf Loos saying "Ornament is
Crime".
I think that learning to write in this style is very
valuable discipline. Sometimes, when you are stuck, you can
try writing New Orleans Style, and sometimes you discover
that form liberates: with a cliched style, and only one way
to do it, it becomes possible to discover that one way,
where as earlier it was like looking for a needle in a
haystack.
For example, suppose you want to be able to nest loops
(dotimes (i1 n1)
(dotimes (i2 n2)
...
...
(dotimes (ir nr)
body of code )))...)))
a depth that varies at run time. One can get badly stuck
thinking about this. Tackling it New Orleans style will
unstick you.
BUT, and it is a big but, worthy of all capital letters,
please be sure to locate this style in a mythical
past. Nobody ever wrote exclusively in this clumsy
style. The point of using a computer language to be
productive, the sooner to achieve an important end, external
to computer science. Never feel guilty about using loop,
make-array, aref, rotatef, shiftf,... all those cheats that
make CL so easy to use to get real work done.
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> Ilya replied:
>
>>>Why?
>>
>>Because I'm learning.
>>I would like to see "pure" code for now.
>>Yes, even if it conses too much and therefore
>>eats CPU and memory.
>
>
>
> ;;; We have a matrix, rows 0,1,...
> ;;; We want to exchange rows i and j
>
> ;;; First we break it into five pieces
>
> ;;; rows 0 to i-1
> ;;; row i
> ;;; row i+1 to j-1
> ;;; row j
> ;;; row j+1 ...
>
> ;;; Then we put it back together
>
> ;;; So we start with a utility function to break off the first n rows
>
> (defun break-off-first-n-rows(n remaining-rows broken-off-already)
> (if (zerop n)(list remaining-rows broken-off-already)
> (break-off-first-n-rows (- n 1)
> (cdr remaining-rows)
> (cons (car remaining-rows)
> broken-off-already))))
>
> (defun break-up (matrix i j)
> (let ((first-break
> (break-off-first-n-rows i matrix '())))
> (let ((row-i (caar first-break))
> (row-i+1-up (cdar first-break)))
> (let ((second-break
> (break-off-first-n-rows (- j (+ i 1))
> row-i+1-up
> '())))
> (let ((mid-section (cadr second-break))
> (row-j (caar second-break))
> (remainder (cdar second-break)))
> (rebuild (cadr first-break)
> (cons row-j
> (rebuild mid-section
> (cons row-i
> remainder)))))))))
>
> (defun rebuild (broken-off-bit already-rebuilt)
> (if broken-off-bit
> (rebuild (cdr broken-off-bit)
> (cons (car broken-off-bit)
> already-rebuilt))
> already-rebuilt))
>
> (break-up '(0 1 2 3 4 5 6 7 8 9) 3 6)
> => (0 1 2 6 4 5 3 7 8 9)
>
> * (break-up '((0.0 0.1)(1.0 1.1)) 0 1)
> => ((1.0 1.1) (0.0 0.1))
What is the advantage of this code over much shorter
and simplier solutions already suggested ?
>
> Exchange columns by transposing the matrix, exchanging the
> rows, transposing the matrix.
Thanks but you are a little late. I figured that just after
writing the transpose function ;)
>
> I much prefer to call this Traditional New Orleans Style
> Lisp, like they wrote in the 1920's. I distrust the practise
> of calling this style "pure functional programming", it
> reminds me too much of Adolf Loos saying "Ornament is
> Crime".
>
> I think that learning to write in this style is very
> valuable discipline.
That's why I'm here ;)
> Sometimes, when you are stuck, you can
> try writing New Orleans Style, and sometimes you discover
> that form liberates: with a cliched style, and only one way
> to do it, it becomes possible to discover that one way,
> where as earlier it was like looking for a needle in a
> haystack.
>
> For example, suppose you want to be able to nest loops
>
> (dotimes (i1 n1)
> (dotimes (i2 n2)
> ...
> ...
> (dotimes (ir nr)
> body of code )))...)))
>
> a depth that varies at run time. One can get badly stuck
> thinking about this. Tackling it New Orleans style will
> unstick you.
I guess ...
>
> BUT, and it is a big but, worthy of all capital letters,
> please be sure to locate this style in a mythical
> past. Nobody ever wrote exclusively in this clumsy
> style. The point of using a computer language to be
> productive, the sooner to achieve an important end, external
> to computer science. Never feel guilty
I don't. But I prefer not to have side effects in functions.
I usually program in PHP. I've seen functions that modify
their arguments - it becomes really messy (or is it because of
skills of average php programmer? Everybody jumps over
the language because it's simple)
> about using loop,
> make-array, aref, rotatef, shiftf,... all those cheats that
> make CL so easy to use to get real work done.
>
> Alan Crowe
> Edinburgh
> Scotland
>
Ilya asked:
> What is the advantage of this code over much shorter and
> simplier solutions already suggested ?
There aren't any.
It is fun to try to code simple problems within
restrictions, such as no assignments.
Writing it was a fun puzzle. Indeed, I've had another go this
morning.
(defun iota (n end)
(if (< n end)
(cons n (iota (+ n 1) end))))
(defun trim-list (n list)
(if (zerop n) list
(trim-list (- n 1) (cdr list))))
(defun pad-list (n list)
(if (zerop n) list
(cons nil
(pad-list (- n 1)
list))))
(defun ensure-length (n list)
(cond ((zerop n) nil)
(t (cons (car list)
(ensure-length (- n 1)
(cdr list))))))
(defun transpose-elements (list r s)
(assert (< r s))
(mapcar (lambda(count lead current lag)
(cond ((= r count) lead)
((= s count) lag)
(t current)))
(iota 0 (length list))
(ensure-length (length list)
(trim-list (- s r) list))
list
(pad-list (- s r) list)))
(transpose-elements '(0 1 2 3 4 5 6 7 8 9) 4 7)
=> (0 1 2 3 7 5 6 4 8 9)
Don't go looking for advantages to this code, it is
pessimal. It is just for fun. Lisp is as good a toy as
Lego (the plastic bricks).
If you must have a utilitarian justification, consider the
note to page 17 on page 402 of Graham's ANSI Common Lisp
Readers who have trouble with the concept of recursion
may want to consult either of the following:
Touretzky, David S. Common Lisp: A Gentle
Introduction to Symbolic Computation
Friedman and Felleisen. The Little Lisper
Clearly there is a problem with learning recursion. I blame
lack of play. Don't let killjoys on comp.lang.lisp
discourage you from playful coding.
Alan
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> Clearly there is a problem with learning recursion. I blame
> lack of play. Don't let killjoys on comp.lang.lisp
> discourage you from playful coding.
Using recursion when the problem is inherently recursive is much easier
to learn and much more important to learn. Using recursion just because
you can isn't that much more sensible than using side-effects just
because you can, but it does put you in a smaller sandbox when you're
playing. Whether this is a good thing is another question. My take is
that if you're going to get wet, you might as well go swimming.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> I much prefer to call this Traditional New Orleans Style
> Lisp, like they wrote in the 1920's. I distrust the practise
> of calling this style "pure functional programming", it
> reminds me too much of Adolf Loos saying "Ornament is
> Crime".
So, what happens on Mardi Gras? Everyone gets out their mutators and
goes wild?
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
ilya <············@example.com> writes:
> Hi all.
>
> [BACKGROUND]
> It's not a homework, just hacking around ;)
> I hope I'll understand better all that Gauss method
> if I implement it ....
>
> [DETAILS]
> Lisp-1 implementation: librep
> Code supposed to do: exchange 2 rows in a matrix
> Matrix representation: list of rows (each row being
> a list of numbers)
>
> The code:
> ####
> (define (xchg-rows m r1 r2) ; (almost?) tail recursive
> (letrec ((kern (lambda (m r1 r2 done r1-replacement r2-replacement)
> (cond
> ((null m)
> done)
> ((= r1 0)
> (kern
> (cdr m) (- r1 1) (- r2 1)
> (cons r1-replacement done) r1-replacement r2-replacement))
> ((= r2 0)
> (kern
> (cdr m) (- r1 1) (- r2 1)
> (cons r2-replacement done) r1-replacement r2-replacement))
> (t
> (kern
> (cdr m) (- r1 1) (- r2 1)
> (cons (car m) done) r1-replacement r2-replacement))))))
> (reverse (kern m r1 r2 '() (nth r2 m) (nth r1 m)))))
> ####
> [QUESTIONS]
> 1. Besides style, any reason that (reverse ..) should go
> inside kern->cond->null m ?
> 2. How can that be simplified ?
By using a two dimensional array for matrix representation.
Bj�rn
Björn Lindberg wrote:
> ilya <············@example.com> writes:
>
>
>>Hi all.
>>
>>[BACKGROUND]
>>It's not a homework, just hacking around ;)
>>I hope I'll understand better all that Gauss method
>>if I implement it ....
>>
>>[DETAILS]
>>Lisp-1 implementation: librep
>>Code supposed to do: exchange 2 rows in a matrix
>>Matrix representation: list of rows (each row being
>>a list of numbers)
[snip]
>>2. How can that be simplified ?
>
>
> By using a two dimensional array for matrix representation.
Thanks.
>
>
> Björn