Hi, dear Lisp way followers!
O'Caml has construction "let rec", which binds variable to
function/value so that it can refer to itself. Examples:
let rec fact n = if 0=n then 1 else n*fact (n-1);;
is recursive factorial definition, and
type intList={car: int; cdr: intList};;
let rec r={ car=10; cdr=r };;
there r is cycled "list": [10,10,10,...].
In Common Lisp, functions defined with defun and labels can refer to
itself too, but variables can't.
I wrote letrec macro for my experiments with lazy evaluation:
(defmacro letrec (arglist . body)
`(let* ,(mapcar #'(lambda (var) (list (first var) nil)) arglist)
,@(mapcar
#'(lambda (var) (list 'setq (first var) (second var)))
arglist)
,@body))
It works if references in right side of binding are lazy (i.e. in
closures), and I don't need more (BTW, refecrences a mutual). But this
macro uses setq, and I don't like it.
One of my ideas was to use labels -- each function for variable, and
reffering to them as function call. But if two "variables" refer to
another, function is called twice, producing two different (eq)
objects. If these objects are deffered computation objects, same
computation is performed twice, slowing down computation :(
Can anyone suggest pure functional solution in Lisp? It seems to me
it is impossible in CL...
--
Ivan Boldyrev remove .microsoft.com from my address
| recursion, n:
| See recursion
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> writes:
> I wrote letrec macro for my experiments with lazy evaluation:
>
> (defmacro letrec (arglist . body)
> `(let* ,(mapcar #'(lambda (var) (list (first var) nil)) arglist)
> ,@(mapcar
> #'(lambda (var) (list 'setq (first var) (second var)))
> arglist)
> ,@body))
>
> It works if references in right side of binding are lazy (i.e. in
> closures), and I don't need more (BTW, refecrences a mutual). But this
> macro uses setq, and I don't like it.
>
> One of my ideas was to use labels -- each function for variable, and
> reffering to them as function call. But if two "variables" refer to
> another, function is called twice, producing two different (eq)
> objects. If these objects are deffered computation objects, same
> computation is performed twice, slowing down computation :(
>
> Can anyone suggest pure functional solution in Lisp? It seems to me
> it is impossible in CL...
It's not impossible, but if you want purely functional you'll have to
use the Y operator and compare the closures with extensional
equivalence rather than intensional (EQ won't do it).
What's wrong with SETQ?
The deferred computation solution seems fine, just memoize the
results.
Joe Marshall <···@ccs.neu.edu> writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> writes:
>
> > I wrote letrec macro for my experiments with lazy evaluation:
> >
> > (defmacro letrec (arglist . body)
> > `(let* ,(mapcar #'(lambda (var) (list (first var) nil)) arglist)
> > ,@(mapcar
> > #'(lambda (var) (list 'setq (first var) (second var)))
> > arglist)
> > ,@body))
> >
> > It works if references in right side of binding are lazy (i.e. in
> > closures), and I don't need more (BTW, refecrences a mutual). But this
> > macro uses setq, and I don't like it.
> >
> > One of my ideas was to use labels -- each function for variable, and
> > reffering to them as function call. But if two "variables" refer to
> > another, function is called twice, producing two different (eq)
> > objects. If these objects are deffered computation objects, same
> > computation is performed twice, slowing down computation :(
> >
> > Can anyone suggest pure functional solution in Lisp? It seems to me
> > it is impossible in CL...
>
> It's not impossible, but if you want purely functional you'll have to
> use the Y operator and compare the closures with extensional
> equivalence rather than intensional (EQ won't do it).
Really, I do not want to compare it. I want to write letrec macro
without setq/setf.
> What's wrong with SETQ?
It is contrary to spirit of pure functional programming :)
> The deferred computation solution seems fine, just memoize the
> results.
My idea with lables was that:
;;; Lazy list of Fibonacci numbers
(defun fibonacci ()
(alazy:letrec
((f1 (alazy:lcons 1 f2))
(f2 (alazy:lcons 1 f3))
(f3 (alazy:lmapcar #'+ f1 f2)))
f1))
was transformed into something like that:
(defun fibonacci ()
(labels
((f1 ()
(alazy:lcons 1 (f2)))
(f2 ()
(alazy:lcons 1 (f3)))
(f3 ()
(alazy:lmapcar #'+ (f1) (f2))))
(f1)))
alazy:lcons, alazy:lmapcar are macro that deffer their arguments. When
alazy:lcar or lcdr are called, result is memoized.
When I call (alazy:lcar (alazy:lcdr (alazy:lcdr (fibonacci)))), f1 and
f2 are called twice (once by lcdr, once by lmapcar), producing
different objects with same content. So, values are re-calculated
twice, producing O(n^2) time instead of O(n).
Memoizing in f1/f2/f3 requires setf/setq again. :(
--
Ivan Boldyrev remove .microsoft.com from my address
Your bytes are bitten.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> writes:
> > > Can anyone suggest pure functional solution in Lisp? It seems to me
> > > it is impossible in CL...
> >
> > It's not impossible, but if you want purely functional you'll have to
> > use the Y operator and compare the closures with extensional
> > equivalence rather than intensional (EQ won't do it).
>
> Really, I do not want to compare it. I want to write letrec macro
> without setq/setf.
You should take a look at
Mayer Goldberg.
"A variadic extension of Curry's fixed-point combinator".
Workshop on Scheme and Functional Programming (2002).
October 2002.
Unfortunately, I don't think you can get that on line, yet. It shows
how to implement an n-ary Y combinator.
Joe Marshall <···@ccs.neu.edu> writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> writes:
>
> > > > Can anyone suggest pure functional solution in Lisp? It seems to me
> > > > it is impossible in CL...
> > >
> > > It's not impossible, but if you want purely functional you'll have to
> > > use the Y operator and compare the closures with extensional
> > > equivalence rather than intensional (EQ won't do it).
> >
> > Really, I do not want to compare it. I want to write letrec macro
> > without setq/setf.
>
> You should take a look at
> Mayer Goldberg.
> "A variadic extension of Curry's fixed-point combinator".
> Workshop on Scheme and Functional Programming (2002).
> October 2002.
>
> Unfortunately, I don't think you can get that on line, yet. It shows
> how to implement an n-ary Y combinator.
http://scheme2002.ccs.neu.edu/more.html
==========================================================
Scheme 2002
We are preparing the papers for the Web. If you need them now, please
send email to Olin Shivers.
==========================================================
--
Ivan Boldyrev remove .microsoft.com from my address
There are 256 symbols in English alphabet.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
> It is contrary to spirit of pure functional programming :)
*CL* is contrary to the spirit of pure functional programming. Sure, you
can do it, but ... why? why not use an FP language if you want to do FP?
--tim
··········@tfeb.org (Tim Bradshaw) writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
>
> > It is contrary to spirit of pure functional programming :)
>
> *CL* is contrary to the spirit of pure functional programming.
Oh, really?
> Sure, you can do it, but ... why? why not use an FP language if
> you want to do FP?
Why use other language if we have Lisp?
--
Ivan Boldyrev remove .microsoft.com from my address
| recursion, n:
| See recursion
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
> Oh, really?
Yes, really. That's why it has SETQ and SETF and GO and side-efects
all over the place. Pure FP languages don't have that stuff.
>
> > Sure, you can do it, but ... why? why not use an FP language if
> > you want to do FP?
>
> Why use other language if we have Lisp?
Erm, because pure FP languages were designed for pure FP and CL
wasn't?
No, I know, that would be too simple. Better to complain about CL.
--tim
··········@tfeb.org (Tim Bradshaw) writes:
> > Oh, really?
>
> Yes, really. That's why it has SETQ and SETF and GO and side-efects
> all over the place. Pure FP languages don't have that stuff.
Well - you _can_ do pure FP, can't you? It's not like the
implementation is expected to sabotage any attempt...
> > Why use other language if we have Lisp?
>
> Erm, because pure FP languages were designed for pure FP and CL
> wasn't?
> No, I know, that would be too simple. Better to complain about CL.
Aren't there any pure functional lisp dialects?
Mario.
In article <··············@cupid.igpm.rwth-aachen.de>, Mario S. Mommer
<········@yahoo.com wrote:
>Aren't there any pure functional lisp dialects?
Google "Peter Henderson Functional Programming". As I recall, he
outlines a functional subset of some then-current Lisp. (The book
was published in 1980.)
All this information provided by the far recesses of my memory;
treat accordingly.
+ Mario S. Mommer <········@yahoo.com>:
| Aren't there any pure functional lisp dialects?
There is DSSSL, which is essentially the functional subset of Scheme
with bunches of primitives added to do interesting things with SGML
parse trees. Not a general purpose programming language, in other
words. (And, of course, there is some debate over whether Scheme is a
Lisp dialect at all, but let's not open that particular can of worms.)
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Yes it works in practice - but does it work in theory?
"Tim Bradshaw" <··········@tfeb.org> wrote in message
·································@posting.google.com...
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message
news:<··············@localhost.localdomain>...
>
> > Oh, really?
>
> Yes, really. That's why it has SETQ and SETF and GO and side-efects
> all over the place. Pure FP languages don't have that stuff.
>
> >
> > > Sure, you can do it, but ... why? why not use an FP language if
> > > you want to do FP?
> >
> > Why use other language if we have Lisp?
>
> Erm, because pure FP languages were designed for pure FP and CL
> wasn't?
> No, I know, that would be too simple. Better to complain about CL.
FWIW, I didn't hear any complaining in Ivan's questions.... then again, I
was probably the last one still talking to Ilias.. :-/
(BTW, your assasins were easily bribed and are now headed back your way.
You must be a very cheap person ;)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
"Coby Beck" <·····@mercury.bc.ca> wrote in message news:<·············@otis.netspace.net.au>...
>
> (BTW, your assasins were easily bribed and are now headed back your way.
> You must be a very cheap person ;)
Those were not the assassins, those were the advance bribe-takers ...
--tim
"Tim Bradshaw" <··········@tfeb.org> wrote
> "Coby Beck" <·····@mercury.bc.ca> wrote in
> >
> > (BTW, your assasins were easily bribed and are now headed back your way.
> > You must be a very cheap person ;)
>
> Those were not the assassins, those were the advance bribe-takers ...
>
> --tim
D'oh!
wow...you're good.
A long time ago, in a galaxy far, far away, Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote:
> ··········@tfeb.org (Tim Bradshaw) writes:
>
>> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
>>
>> > It is contrary to spirit of pure functional programming :)
>>
>> *CL* is contrary to the spirit of pure functional programming.
>
> Oh, really?
Yes, really.
"Pure functional programming" eschews assignment and modification of
values, so that the CL thing of having places and the use of operators
like "setf" is quite totally incompatible with that.
If you use setf in your programs, you're not working "in the spirit of
pure FP."
That's a pretty reasonable position. Haskell fans might go further,
and claim that "pure FP" requires lazy evaluation so that if you're
not writing all your code using the SERIES package, you're not doing
"pure FP."
Scheme is usually not used in a terribly "pure" fashion, either, what
with functions like set-cdr! and such. It tends to be a bit closer to
the FP model than Common Lisp, as it encourages "applicative" idioms
that CL tends to do in other ways.
The notion that Common Lisp is a "pure functional language" is as true
as the notion that C++ is a "pure object oriented language."
Entertainingly, the emergence of STL, in C++, actually leads to a
programming model that looks somewhat like the "generic programming"
common to the use of CLOS. (The author of STL pretty much decries the
use of object oriented programming, which is pretty funny...)
--
If this was helpful, <http://svcs.affero.net/rm.php?r=cbbrowne> rate me
http://www3.sympatico.ca/cbbrowne/lisp.html
"The surest sign that intelligent life exists elsewhere in the
universe is that it has never tried to contact us."
-- Calvin and Hobbes
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
> Hi, dear Lisp way followers!
>
> O'Caml has construction "let rec", which binds variable to
> function/value so that it can refer to itself. Examples:
This is probably inspired by the Scheme construct letrec. Scheme has a
single binding namespace for functions and variables, so a construct
which provides that scoping rule for lambdas
> let rec fact n = if 0=n then 1 else n*fact (n-1);;
>
> is recursive factorial definition, and
>
> type intList={car: int; cdr: intList};;
> let rec r={ car=10; cdr=r };;
That's crazy! By what twisted evaluation rule do you have an
established binding for the variable r at the point where the cdr
field is initialized? It means that the object must be halfway
constructed so that its address can be assigned to r, and then the
initialization of the fields takes place. Blech!
Is this really valid O'Caml or just overactive imagination on
someone's part? ;)
> there r is cycled "list": [10,10,10,...].
Can you think of an actual useful example, other than a cyclic list?
> In Common Lisp, functions defined with defun and labels can refer to
> itself too, but variables can't.
Probably because this is much more useful for functions than for
variables. If an ordinary expression tries to evaluate the variable to
which its result is about to be bound, that is useless, because its
job is to compute that initial value. So what does that leave you? The
possibility of capturing the (uninitialized) binding for later
evaluation in a closure:
(letrec ((x (lambda () ... x))) ...)
What does this buy you that labels does not? You get indirection; the
ability to assign a different function-object to x, so that (funcall
x) can call a different function. If you don't plan to modify x, then
I don't see what advantage there is compared to making a function
binding for the symbol x.
Since you are so concerned with purity, it can't be destructive
modification you are after!
What is the actual high level problem that you are trying to solve?
> closures), and I don't need more (BTW, refecrences a mutual). But this
> macro uses setq, and I don't like it.
[ snip ]
> Can anyone suggest pure functional solution in Lisp? It seems to me
> it is impossible in CL...
What is your problem? Your macro *hides* the use of SETQ. Purity is a
myth; it relies on sweeping impure things under the carpet.
You do know that when your computer executes a functional language, it
still has to carry out millions of destructive register-register and
register-memory data movement instructions?
Creating a variable binding in a functional language still requires a
piece of memory, which previously contained something else. How does
the new value get there?
Functional programming is about passing some concerns to the machine,
not about eliminating those concerns from the face of reality.
Writing a macro is one form of passing concerns to the machine. You
don't have to view the macroexpansion as being the program you are
writing any more than you have to view the compiled machine code as
being the program you are writing.
···@ashi.footprints.net (Kaz Kylheku) writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote
> > Hi, dear Lisp way followers!
> >
> > O'Caml has construction "let rec", which binds variable to
> > function/value so that it can refer to itself. Examples:
>
> This is probably inspired by the Scheme construct letrec. Scheme has
> a single binding namespace for functions and variables, so a
> construct which provides that scoping rule for lambdas
>
> > let rec fact n = if 0=n then 1 else n*fact (n-1);;
> >
> > is recursive factorial definition, and
> >
> > type intList={car: int; cdr: intList};;
> > let rec r={ car=10; cdr=r };;
>
> That's crazy! By what twisted evaluation rule do you have an
> established binding for the variable r at the point where the cdr
> field is initialized? It means that the object must be halfway
> constructed so that its address can be assigned to r, and then the
> initialization of the fields takes place. Blech!
Exactly. But see also Larry Clapp's posting about #1= and #1#.
> Is this really valid O'Caml or just overactive imagination on
> someone's part? ;)
I always test my examples before posting :)
> > there r is cycled "list": [10,10,10,...].
>
> Can you think of an actual useful example, other than a cyclic list?
Lazy list of primes use yourself to generate new prime. There is
circular dependency.
let rec nextprime n lizt start pl prefitem p2 =
if 0 = prefitem then
if n<p2 then
Next { lcar=n; lcdr=lazy (nextprime (n+2) start start pl pl p2) }
else
let pn = lcar lizt in
nextprime n lizt start (pl+1) 1 (pn*pn)
else
let p = lcar lizt in
if 0=(n mod p) then
nextprime (n+2) start start pl pl p2
else
match lcdr lizt with
Next v -> nextprime n v start pl (prefitem-1) p2;;
let rec primes = { lcar=2; lcdr=lazy (nextprime 3 primes primes 1 0 9) };;
(9 is square of 3; 3 is next prime. I use p2 for optimization. Idea is
from "Algoritmique Alge'brique" by P. Naudin and C. Quitte'. I have
Russian translation).
> > In Common Lisp, functions defined with defun and labels can refer to
> > itself too, but variables can't.
>
> Probably because this is much more useful for functions than for
> variables. If an ordinary expression tries to evaluate the variable to
> which its result is about to be bound, that is useless, because its
> job is to compute that initial value. So what does that leave you? The
> possibility of capturing the (uninitialized) binding for later
> evaluation in a closure:
>
> (letrec ((x (lambda () ... x))) ...)
>
> What does this buy you that labels does not? You get indirection; the
> ability to assign a different function-object to x, so that (funcall
> x) can call a different function. If you don't plan to modify x, then
> I don't see what advantage there is compared to making a function
> binding for the symbol x.
For example, when I pass variable value twice to another functions, I
pass same object (struct lazy-recipe), and at second time it is
evaluated and memoized (I do it with setq, BTW :). When I use
function, two diffrent objects are generated, and same value is
calculated twice. Result of calculation is same, but time is O(n^2),
not O(n), for example.
> Since you are so concerned with purity, it can't be destructive
> modification you are after!
My English is not good enough to understant this phrase :(
> What is the actual high level problem that you are trying to solve?
>
> > closures), and I don't need more (BTW, refecrences a mutual). But this
> > macro uses setq, and I don't like it.
>
> [ snip ]
>
> > Can anyone suggest pure functional solution in Lisp? It seems to me
> > it is impossible in CL...
>
> What is your problem? Your macro *hides* the use of SETQ. Purity is a
> myth; it relies on sweeping impure things under the carpet.
OK, it hides. But think of it as task from textbook :)
> You do know that when your computer executes a functional language, it
> still has to carry out millions of destructive register-register and
> register-memory data movement instructions?
I like to compile-and-disassemble my code with CMU CL. :)
> Creating a variable binding in a functional language still requires a
> piece of memory, which previously contained something else. How does
> the new value get there?
It's problem of implementation, not theory :)
> Functional programming is about passing some concerns to the machine,
> not about eliminating those concerns from the face of reality.
> Writing a macro is one form of passing concerns to the machine. You
> don't have to view the macroexpansion as being the program you are
> writing any more than you have to view the compiled machine code as
> being the program you are writing.
OK, sounds great, :) but I want to learn limits of pure functional
subset of Lisp. Not computational limits, but expressiveness limits.
--
Ivan Boldyrev remove .microsoft.com from my address
Today is the first day of the rest of your life.
···@ashi.footprints.net (Kaz Kylheku) writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
>
> > is recursive factorial definition, and
> >
> > type intList={car: int; cdr: intList};;
> > let rec r={ car=10; cdr=r };;
>
> That's crazy! By what twisted evaluation rule do you have an
> established binding for the variable r at the point where the cdr
> field is initialized? It means that the object must be halfway
> constructed so that its address can be assigned to r, and then the
> initialization of the fields takes place. Blech!
That isn't so crazy, we Lisp hackers do this all the time. (But not
generally to CONS cells!) Any time you have LABELS in a function or
any time you have mutually recursive functions at top level you are
depending on the binding being established before the value is fully
constructed. At top level, the `binding' is established when READ
interns a symbol without a function value, and it is only after the
function value is constructed by the compiler that the initialization
of the function value takes place. It isn't odd for a function to
refer to functions that are not yet defined, or for functions to refer
to themselves. It is a little odd to create data this way, though.
It is easier to do this in a lazy language. Functions are generally
lazy even in an eager language, precisely so you can get away with
having a function refer to itself or functions that are defined later
on.
> > there r is cycled "list": [10,10,10,...].
>
> Can you think of an actual useful example, other than a cyclic list?
Yes. Computing fixed-points where you want to create an inifinite
list of (0 (f 0) (f (f 0)) (f (f (f 0))) ...)
(let ((fixed-point (cons 0 (map 'list f fixed-point))))
....)
from there we use general recursion...
> What does this buy you that labels does not?
Parsimony, but at the expense of efficiency. CL *could* have been a
lazy language, but it isn't. Lazy languages are hard to implement
efficiently.
> What is your problem? Your macro *hides* the use of SETQ. Purity is a
> myth; it relies on sweeping impure things under the carpet.
I think the original poster is experimenting with pure functional
programming and using CL as the vehicle. Perhaps CL isn't the *ideal*
vehicle for this, and perhaps pure functional programming is just an
academic exercise, but the original poster *could* have decided to use
Java or something worse.
I wouldn't recommend that he write production code this way in Common
Lisp, but I don't think he's trying to do that. It's better that he
use (and abuse) Common Lisp for this task than, say Java. Who knows,
he might discover something interesting and get some publicity for
CL.
In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
> O'Caml has construction "let rec", which binds variable to
> function/value so that it can refer to itself. Examples:
>
> let rec fact n = if 0=n then 1 else n*fact (n-1);;
>
> is recursive factorial definition, and
>
> type intList={car: int; cdr: intList};;
> let rec r={ car=10; cdr=r };;
>
> there r is cycled "list": [10,10,10,...].
>
> In Common Lisp, functions defined with defun and labels can
> refer to itself too, but variables can't.
Just by the way, yes they can. To use your r example:
(let ((*print-circle* t)
(r '#1=(10 #1#)))
(print r)
:done)
See "2.4.8.15 Sharpsign Equal-Sign" and "2.4.8.16 Sharpsign
Sharpsign" in the Hyperspec[1].
-- Larry
[1] http://www.lispworks.com/reference/HyperSpec/Front/index.htm.
Larry Clapp <·····@theclapp.org> writes:
> In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
> > O'Caml has construction "let rec", which binds variable to
> > function/value so that it can refer to itself. Examples:
> >
> > let rec fact n = if 0=n then 1 else n*fact (n-1);;
> >
> > is recursive factorial definition, and
> >
> > type intList={car: int; cdr: intList};;
> > let rec r={ car=10; cdr=r };;
> >
> > there r is cycled "list": [10,10,10,...].
> >
> > In Common Lisp, functions defined with defun and labels can
> > refer to itself too, but variables can't.
>
> Just by the way, yes they can. To use your r example:
>
> (let ((*print-circle* t)
> (r '#1=(10 #1#)))
> (print r)
> :done)
First, I can't use it for mutually recursive values (see example of
lazy Fibonacci list), second, I can't use it in macro -- #-characters
are evaluated when macro is read, but not when macro is called.
--
Ivan Boldyrev remove .microsoft.com from my address
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
> lazy Fibonacci list), second, I can't use it in macro -- #-characters
> are evaluated when macro is read, but not when macro is called.
When the effect of "#=" is wanted beyond read time,
functions such as rplacd can be used. E.g.
(let ((r '(1 2 3)))
(rplacd (last r) r)
(dotimes (i 20)
(princ (nth i r))))
==> 12312312312312312312
········@yahoo.com (Eric Smith) writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote
>
> > lazy Fibonacci list), second, I can't use it in macro -- #-characters
> > are evaluated when macro is read, but not when macro is called.
>
> When the effect of "#=" is wanted beyond read time,
> functions such as rplacd can be used. E.g.
>
> (let ((r '(1 2 3)))
> (rplacd (last r) r)
> (dotimes (i 20)
> (princ (nth i r))))
>
> ==> 12312312312312312312
rplacd is same as setf.
--
Ivan Boldyrev remove .microsoft.com from my address
Your bytes are bitten.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<··············@localhost.localdomain>...
> rplacd is same as setf.
In what way? In that it's not pure functional?
If you want pure functional code in CL, you can
simply hide the impure code in macros. Every
pure functional language has impure code behind
the scenes doing the real work. Macros let you
construct any kind of pure language, whether pure
functional or pure anything else, for experiments
such as yours. The advantage of CL over other
languages for that is that its macros are the
most powerful and general, making it easiest to
do the work of implementing any particular pure
language you might want to experiment with.
Replying to Ivan, whose message hasn't hit my newsserver yet:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in
> message news:<··············@localhost.localdomain>...
>> rplacd is same as setf.
Well, then download the source to OCaml from http://caml.inria.fr
and see how they do "let rec", and then do something similar.
In article <····························@posting.google.com>,
········@yahoo.com (Eric Smith) wrote:
>Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message
news:<··············@localhost.localdomain>...
>
>> rplacd is same as setf.
>
>In what way?
Meaning that
(setf (cdr (last r)) r)
macroexpands to
(rplacd (last r) r)
conceptually speaking.
····@vanderbilt.edu (sv0f) writes:
> In article <····························@posting.google.com>,
> ········@yahoo.com (Eric Smith) wrote:
>
> >Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message
> news:<··············@localhost.localdomain>...
> >
> >> rplacd is same as setf.
> >
> >In what way?
>
> Meaning that
> (setf (cdr (last r)) r)
> macroexpands to
> (rplacd (last r) r)
> conceptually speaking.
(modulo return value ... keep in mind that these return different things.
but yes, ... "conceptually")
Oooh. Scary. So what it expands into determines its linguistic character?
Does it bother anyone in this discussion that all the FP in the world
"expands" into machine instructions that perform side effects on the
actual machine state? (Sorry if I burst anyone's bubble. Maybe
someone had the lingering theory that new machines were being consed
with each FP operation...)
I offer this, by the way, not primarily to be sarcastic, though
perhaps it sounds that way, but rather as a kind of existence proof
that illusions matter, and when you shatter illusions, you also
shatter the carefully constructed drama of meaning. Consequently,
what something expands to is not a good way of judging what something
means...
Kent M Pitman <······@world.std.com> wrote in message news:<···············@shell01.TheWorld.com>...
> Does it bother anyone in this discussion that all the FP in the world
> "expands" into machine instructions that perform side effects on the
> actual machine state?
Yes, me. See ····························@posting.google.com .
:)
In article <···············@shell01.TheWorld.com>, Kent M Pitman
<······@world.std.com> wrote:
>Does it bother anyone in this discussion that all the FP in the world
>"expands" into machine instructions that perform side effects on the
>actual machine state?
!
(Runs from the room screaming; the world will never be the same.
Someone (Backus?) must pay.)
Kent M Pitman <······@world.std.com> writes:
> Does it bother anyone in this discussion that all the FP in the world
> "expands" into machine instructions that perform side effects on the
> actual machine state? (Sorry if I burst anyone's bubble. Maybe
> someone had the lingering theory that new machines were being consed
> with each FP operation...)
But wait. Since every fundamental particle within the computer is
indistinguishable from any other of the same type (all electrons look
the same) so maybe a new universe is being consed for each
computation. Since the old one becomes inaccessible I suppose you
could use a little linear logic to optimize it.....
In article <···············@shell01.TheWorld.com>, Kent M Pitman wrote:
> Does it bother anyone in this discussion that all the FP in the
> world "expands" into machine instructions that perform side
> effects on the actual machine state?
Yes.
I wrote earlier something about "download the OCaml source and do
it the way they do it." I did download the OCaml source (well,
*an* OCaml source), but couldn't find where they did it, so I
couldn't post code that I strongly suspect has *gasp* an
assignment in it.
I find Mr. Boldyrev's attitude (about setq and other
side-effects) quite silly, and I think it practically begs for an
Erik-Naggum-esque rant along the lines of "when in Rome, do as
the Romans do" and/or "reexamine your prejudices" and/or "upgrade
your brain." Of course, we can all probably imagine such a rant
for ourselves in sufficient glorious (ahem) detail; sadly, unless
Ivan has lurked here a lot longer than his posting history at
Google Groups suggests, he cannot.
As Kaz Kylheku pointed out,
> Creating a variable binding in a functional language still
> requires a piece of memory, which previously contained
> something else. How does the new value get there?
Ivan responded:
> It's problem of implementation, not theory :)
From which I suppose we can deduce that if you implement his
desired "letrec" in C, he won't mind, but if you do it with a
macro in *gasp again* actual Lisp, he will (and, in fact, does).
For myself, I can imagine some sort of code-walker that descends
an assigned list, replacing textual references in the code with
real references to the data structure, a-la #1= and #1#, but such
a thing breaks at the very top level of the data structure, with
e.g. something as simple as
(letrec ((a (cons a a)))
; ...
)
Ivan would apparently have cons *predict* the location of the
cell it's about to get so that it can use that address in the
initialization of the cell, because, of course, rplaca and rplacd
"aren't functional programming".
-- Larry
········@yahoo.com (Eric Smith) writes:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote
>
> > rplacd is same as setf.
>
> In what way? In that it's not pure functional?
> If you want pure functional code in CL, you can
> simply hide the impure code in macros.
And I do it.
> Every
> pure functional language has impure code behind
> the scenes doing the real work. Macros let you
> construct any kind of pure language, whether pure
> functional or pure anything else, for experiments
> such as yours. The advantage of CL over other
> languages for that is that its macros are the
> most powerful and general, making it easiest to
> do the work of implementing any particular pure
> language you might want to experiment with.
You do not understand my question. My question is mostly theoretical
:) It is in spirit of textbooks: "Do aaa without using bbb". This
problem seem to be untrivial and interesting (for me, and I hope, for
others too :) I like to do thing without setfs -- it stimulates my
brain :) But when other do setf, I never complain.
I read book, find tasks and implement solutions in different
languages. Just for fun, it's a game. And CL is one of my favourite
toys. :)
--
Ivan Boldyrev remove .microsoft.com from my address
| recursion, n:
| See recursion
In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
> Larry Clapp <·····@theclapp.org> writes:
>> In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
>> > O'Caml has construction "let rec", which binds variable to
>> > function/value so that it can refer to itself. Examples:
>> >
>> > let rec fact n = if 0=n then 1 else n*fact (n-1);;
>> >
>> > is recursive factorial definition, and
>> >
>> > type intList={car: int; cdr: intList};;
>> > let rec r={ car=10; cdr=r };;
>> >
>> > there r is cycled "list": [10,10,10,...].
>> >
>> > In Common Lisp, functions defined with defun and labels can
>> > refer to itself too, but variables can't.
>>
>> Just by the way, yes they can. To use your r example:
>>
>> (let ((*print-circle* t)
>> (r '#1=(10 #1#)))
>> (print r)
>> :done)
>
> First, I can't use it for mutually recursive values (see
> example of lazy Fibonacci list), second, I can't use it in
> macro -- #-characters are evaluated when macro is read, but not
> when macro is called.
So, you'd like
(letrec ((*print-circle* t)
(a (list 'val1 a))
(b (list 'val2 a)))
(print (list a b))
:done)
to turn into a macro that looks like this
(let ((var1 (gensym))
(var2 (gensym)))
`(let* ((*print-circle* t)
(,var1 (list 'val1 nil))
(,var2 (list 'val2 nil))
(a (rplacd ,var1 ,var1))
(b (rplacd ,var2 ,var1)))
(print (list a b))
:done))
which expands to
(LET* ((*PRINT-CIRCLE* T)
(#:G969 (LIST 'VAL1 NIL))
(#:G970 (LIST 'VAL2 NIL))
(A (RPLACD #:G969 #:G969))
(B (RPLACD #:G970 #:G969)))
(PRINT (LIST A B))
:DONE)
which prints
(#1=(VAL1 . #1#) (VAL2 . #1#))
(and returns :DONE).
Would that accurately model what you want? Or do you not like
the RPLACDs either? If not, why? Surely O'Caml must do
something similar internally?
-- Larry
In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
> Larry Clapp <·····@theclapp.org> writes:
>> In article <··············@localhost.localdomain>, Ivan Boldyrev wrote:
>> > In Common Lisp, functions defined with defun and labels can
>> > refer to itself too, but variables can't.
>>
>> Just by the way, yes they can. To use your r example:
>>
>> (let ((*print-circle* t)
>> (r '#1=(10 #1#)))
>> (print r)
>> :done)
>
> First, I can't use it for mutually recursive values (see
> example of lazy Fibonacci list)
True ...
> second, I can't use it in macro -- #-characters are evaluated
> when macro is read, but not when macro is called.
So if you could, you would?
You realize, of course, that READ must use rplaca or rplacd, or
something like them, to perform the function of #n#, I hope?
So if a system function uses them, you don't mind, but if your
function uses them, you do?
-- Larry