Home > Archive > Scheme > April 2005 > Call/cc and side effects
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Call/cc and side effects
|
|
| Nils M Holm 2005-04-06, 12:26 pm |
|
While re-writing some applications of call/cc to CPS, it occurred
to me that call/cc may be considered a generalized form of the
Y-combinator:
((call/cc y) x) = ((lambda (k) (k (y k))) x)
Given this equivalence, how can call/cc be said to cause side effects
in (otherwise?) purely functional programs?
Am I missing something essential?
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Anton van Straaten 2005-04-06, 12:26 pm |
| Nils M Holm wrote:
>
> While re-writing some applications of call/cc to CPS, it occurred
> to me that call/cc may be considered a generalized form of the
> Y-combinator:
>
> ((call/cc y) x) = ((lambda (k) (k (y k))) x)
I think you did that rewrite incorrectly (or else I'm not following what
you're trying to show). The continuation passed to y on the left hand side
should look like ([] x), i.e. (lambda (z) (z x)). Where has that
continuation gone in your right hand side? And why is x on the RHS being
treated as though it were a continuation?
Anton
| |
| Amr Sabry 2005-04-06, 12:26 pm |
| Nils M Holm <nmh@despammed.com> writes:
> While re-writing some applications of call/cc to CPS, it occurred
> to me that call/cc may be considered a generalized form of the
> Y-combinator:
>
> ((call/cc y) x) = ((lambda (k) (k (y k))) x)
The correct equivalence is:
((call/cc y) x)
=
(call/cc (lambda (k)
((y (lambda (a) (k (a x)))) x)))
> Given this equivalence, how can call/cc be said to cause side effects
> in (otherwise?) purely functional programs?
There are several ways to argue that call/cc introduces side-effects. The two
most common ones are:
- Some equivalences between pure functional programs are broken by
call/cc. See: On the expressiveness of programming languages by Matthias
Felleisen.
- Pure (typed) functional programs are isomorphic to intuitionistic
language; add call/cc and they become isomorphic to classical logic. In
other words, call/cc adds something fundamentally new to the
language. See: A formulae-as-types notion of control by Tim Griffin.
--Amr
| |
| Nils M Holm 2005-04-06, 12:26 pm |
| Anton van Straaten <anton@appsolutions.com> wrote:
> Nils M Holm wrote:
>
> I think you did that rewrite incorrectly (or else I'm not following what
> you're trying to show). The continuation passed to y on the left hand side
> should look like ([] x), i.e. (lambda (z) (z x)). Where has that
> continuation gone in your right hand side? And why is x on the RHS being
> treated as though it were a continuation?
I see. What I meant was
((call/cc y)) = ((lambda (k) ((y k) k)) x)
which works fine as long as y = (lambda (k) k), giving the Y combinator:
((call/cc (lambda (k) k)) (lambda (x) x))
= ((lambda (k) (((lambda (k) k) k) k)) (lambda (x) x))
= ((lambda (k) (k k)) (lambda (x) x))
= ((lambda (x) x) (lambda (x) x))
= (lambda (x) x)
It fails for virtually all other cases, though. So: sorry for wasting
bandwidth.
However, my question remains: If call/cc /can/ be re-written using CPS,
how can it introduce side effects (given that the program has no side
effects other than that in question, namely call/cc).
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Matthias Blume 2005-04-06, 12:26 pm |
| Nils M Holm <nmh@despammed.com> writes:
> However, my question remains: If call/cc /can/ be re-written using CPS,
> how can it introduce side effects (given that the program has no side
> effects other than that in question, namely call/cc).
Notice that CPS conversion is a /global/ rewrite of the program.
/Any/ side effect can be eliminated using a global rewrite. (In some
sense you can take this as a "definition" of "side effects": something
that cannot be explained locally but only globally.)
Matthias
| |
| Nils M Holm 2005-04-08, 8:59 am |
| Matthias Blume <find@my.address.elsewhere> wrote:
> Notice that CPS conversion is a /global/ rewrite of the program.
> /Any/ side effect can be eliminated using a global rewrite. (In some
> sense you can take this as a "definition" of "side effects": something
> that cannot be explained locally but only globally.)
Ok, I see that the possibility to CPS-transform call/cc proves nothing.
However, my intuition still tells me that call/cc cannot introduce side
effects in purely applicative programs. Let me explain why:
Definition:
(1) A purely applicative program uses the following procedures
exclusively: CAR CDR COND CONS EQ? LET LAMBDA LIST PAIR? QUOTE.
Assumption:
- The only observable side effect in a purely applicative program would
be a function f that delivers different values when passed the same
actual argument multiple times, eg
(cons (f #t) (f #t)) => (#t . #f)
I think that call/cc cannot be used to implement above side effect
without using procedures other than those given in (1).
In particular, I think that SET! would be required to implement above
behaviour, but in this case, the side effect would be caused by SET!
itself.
Of course, I am aware of the fact that (k 'foo) returns non-locally
in
(call/cc (lambda (k) (whatever ((lambda (z) (z (k 'foo))) x))))
which is a side effect by Matthias' above definition. However, since
there are no non-local effects other than that caused by (the application
of the continuations captured by) call/cc itself, applying k renders all
effects of x (whatever x is) undone.
When call/cc returns, the entire state of the program is (almost) equal
to the state that was in effect at the time where call/cc was applied,
the /only/ difference being that call/cc now returns a value.
Hence applying a captured continuation in an otherwise purely
applicative program transfers control not just to a different location,
but also to an /earlier point in the history of the computation/ being
performed (thereby going 'back in time' as it were).
This way a computation is resumed - or performed - with a value passed
to it, which sounds like an ordinary function application to me.
This in turn makes me think that call/cc does not make any difference
at all in (otherwise?) purely applicative programs, because everything
that can be expressed using call/cc can also be expressed by using
application exclusively.
In case I am completely mistaken, I would be highly interested in a
counter-example.
Thank you for your attention.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| szgyg@ludens.elte.hu 2005-04-08, 4:01 pm |
| In article <d35h51$hgt$1@online.de>, Nils M Holm <nmh@despammed.com> writes:
>
> Definition:
>
> (1) A purely applicative program uses the following procedures
> exclusively: CAR CDR COND CONS EQ? LET LAMBDA LIST PAIR? QUOTE.
>
> Assumption:
>
> - The only observable side effect in a purely applicative program would
> be a function f that delivers different values when passed the same
> actual argument multiple times, eg
>
> (cons (f #t) (f #t)) => (#t . #f)
>
> I think that call/cc cannot be used to implement above side effect
> without using procedures other than those given in (1).
(let ((f (lambda (x)
(call/cc (lambda (k) k))))
(cons (f) (f)))
> This in turn makes me think that call/cc does not make any difference
> at all in (otherwise?) purely applicative programs, because everything
> that can be expressed using call/cc can also be expressed by using
> application exclusively.
Because lambda-calculi is Turing-complete, _everything_ can be expressed
by using application exclusively.
--
Side effect? What's that? Use Haskell!
| |
| Amr Sabry 2005-04-08, 4:01 pm |
| Nils M Holm <nmh@despammed.com> writes:
> - The only observable side effect in a purely applicative program would
> be a function f that delivers different values when passed the same
> actual argument multiple times, eg
Continuations are a much more expressive effect than assignments. In other
words, you can express assignments with continuations. You might want to
check Filinski's 1994 paper on "Representing Monads."
For the specific example you mention above, try looking at the Thielecke's
1999 paper on "Using a Continuation Twice and Its Implications for the
Expressive Power of Call/CC." He shows a term M where:
((lambda (x) (cons x x)) M)
is NOT THE SAME as:
(((lambda (x) (lambda (y) (cons x y)) M)) M)
--Amr
| |
| Anton van Straaten 2005-04-09, 8:58 am |
| Nils M Holm wrote:
> Assumption:
>
> - The only observable side effect in a purely applicative program
> would be a function f that delivers different values when passed
> the same actual argument multiple times, eg
'szgyg' already gave a function which I'll rewrite as:
(define f (lambda (x) (call/cc (lambda (k) k))))
(eq? (f 0) (f 0)) => #f
There you have "different values when passed the same actual argument
multiple times".
But re the definition of side effect, what about referential
transparency? In the following expression:
(call/cc (lambda (k) (cons (k 1) (k 2))))
....you can't simply substitute values for (k 1) and/or (k 2) and get the
correct result.
So, even if it weren't for functions like the first one above, you'd
have to explain this behavior in your purely applicative program. If
that's not a side effect, what do you call it, and how do you justify
the loss of referential transparency?
This may just be an example of Matthias' definition of a side effect,
but I find it quite compelling, mainly because I don't know how to
answer the referential transparency question without throwing up my
hands and saying "let's call it a side effect". If there are any clever
theoretical answers which define this as something other than a side
effect, I'm curious to hear them.
Anton
| |
| Jussi Piitulainen 2005-04-09, 8:58 am |
| Anton van Straaten writes:
> 'szgyg' already gave a function which I'll rewrite as:
>
> (define f (lambda (x) (call/cc (lambda (k) k))))
> (eq? (f 0) (f 0)) => #f
>
> There you have "different values when passed the same actual
> argument multiple times".
That does not seem different from:
(define f (lambda (x) (cons x x)))
(eq? (f 0) (f 0)) => #f
Call/cc does not add anything here. I would be curious to see if there
is a solution, with or without call/cc but without set!, to what Nils
actually asked:
(cons (f #t) (f #t)) => (#t . #f)
I failed to find one, but I'm really not that familiar with call/cc
and cannot afford to spend the time to learn it now. Just curious.
| |
| oleg@pobox.com 2005-04-09, 8:58 am |
|
Nils M Holm wrote:
> (1) A purely applicative program uses the following procedures
> exclusively: CAR CDR COND CONS EQ? LET LAMBDA LIST PAIR? QUOTE.
> - The only observable side effect in a purely applicative program
would
> be a function f that delivers different values when passed the
same
> actual argument multiple times
You don't need call/cc to produce an observable side-effect in a
``pure applicative program'' that satisfies the above
definition. Example:
(eq? (list list) (list list)) ; ==> #f
R5RS requires 'list' invoked with at least one argument to produce a
_fresh_ list, which can be distinguished with eq?. Ditto for cons:
(eq? (cons car cdr) (cons car cdr)) ; ==> #f
OK, you may say: let's add integer constants, let's replace eq? with
'=' (which can be applied to integers only). If we add call/cc, can we
still write a thunk, which, when evaluated twice, gives two different
integers?
Yes, we can:
(let ((r
(call-with-current-continuation
(lambda (k) (cons k 1)))))
(let ((f (lambda ()
(let ((v (cdr r)))
;(display "invoking f:") (display v) (newline)
(case v
((1) v)
((2) ((car r) v)))))))
(list
(if (= (cdr r) 1) (f) #f)
(if (= (cdr r) 1) (call-with-current-continuation
(lambda (kn) ((car r) (cons kn 2))))
(f)))))
The commented out display statements can be uncommented to show
that the thunk f is indeed invoked twice. Here's the result, with the
display statements uncommented:
invoking f:1
invoking f:2
(1 2)
I used Scheme48, Petite Chez and SCM systems. It seems that the thunk
'f' is indeed invoked twice, and it produced two different integers.
BTW, Amr Sabry wrote a paper
What is a Purely Functional Language? In J. Functional
Programming, 8(1), 1-22, Jan. 1998.
http://www.cs.indiana.edu/~sabry/pa...lyFunctional.ps
which, btw, mentions that attempts to explain what is pure functional
leads to confusion and disagreement on comp.lang.functional. I guess
in retrospect he should have added comp.lang.scheme...
BTW, you don't have to do CPS transform of complex expressions by
hand. Here's a macro that can do that for you, quite efficiently, with
all administrative redexes reduced:
http://pobox.com/~oleg/ftp/Scheme/m...proof-assistant
| |
| Nils M Holm 2005-04-09, 8:58 am |
| Anton van Straaten <anton@appsolutions.com> wrote:
> (define f (lambda (x) (call/cc (lambda (k) k))))
> (eq? (f 0) (f 0)) => #f
True, but
((f 0) x) = ((f 0) x)
which indicates to me that both (f 0)s are (different instances of)
the same function - much in the same way as '(x y z) and '(x y z) are
different instances of the same list. I would consider them equal,
even if they are not eq?.
> But re the definition of side effect, what about referential
> transparency? In the following expression:
>
> (call/cc (lambda (k) (cons (k 1) (k 2))))
>
> ...you can't simply substitute values for (k 1) and/or (k 2) and get the
> correct result.
This is a good point. I will think about it.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Nils M Holm 2005-04-09, 8:58 am |
| szgyg@ludens.elte.hu wrote:
> In article <d35h51$hgt$1@online.de>, Nils M Holm <nmh@despammed.com> writes:
> (let ((f (lambda (x)
> (call/cc (lambda (k) k))))
> (cons (f) (f)))
Please see my reply to Antons posting.
> Because lambda-calculi is Turing-complete, _everything_ can be expressed
> by using application exclusively.
I would say that you cannot express mutation by application.
(And not even by application plus call/cc.)
Proofs to the contrary are welcome.
You can, however, use a purely applicative language L to write
an interpreter that implements L plus mutation. This interpreter
would interpret a language other than L, though.
Turing-completeness does not imply that things are implemented
easily.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Matthias Blume 2005-04-09, 3:57 pm |
| Jussi Piitulainen <jpiitula@ling.helsinki.fi> writes:
> Anton van Straaten writes:
>
>
> That does not seem different from:
>
> (define f (lambda (x) (cons x x)))
> (eq? (f 0) (f 0)) => #f
Indeed, this is no different and shows that CONS has a side effect in
Scheme which can be observed with EQ?.
| |
| Al-Qaeda Petrofsky 2005-04-09, 8:57 pm |
|
> Nils M Holm wrote:
oleg@pobox.com writes:
[... explanation of why the combination of CONS and EQ? is not
functional ...]
[color=darkred]
> OK, you may say: let's add integer constants, let's replace eq? with
> '=' (which can be applied to integers only). If we add call/cc, can
> we still write a thunk, which, when evaluated twice, gives two
> different integers?
>
> Yes, we can:
>
> (let ((r
> (call-with-current-continuation
> (lambda (k) (cons k 1)))))
> (let ((f (lambda ()
> (let ((v (cdr r)))
> ;(display "invoking f:") (display v) (newline)
> (case v
> ((1) v)
> ((2) ((car r) v)))))))
>
> (list
> (if (= (cdr r) 1) (f) #f)
> (if (= (cdr r) 1) (call-with-current-continuation
> (lambda (kn) ((car r) (cons kn 2))))
> (f)))))
> The commented out display statements can be uncommented to show
> that the thunk f is indeed invoked twice.
YOU'RE FIRED!
Okay, I'll be fair. You did belatedly C.Y.A. in the next paragraph:
> ... It seems that the thunk 'f' is indeed invoked twice, and it
> produced two different integers.
It seems that YOU'RE FIRED!
That's not "a thunk" nor "the thunk". Those are two *different*
thunks, bound to f in *different* environments, whose invocations are
returning two different integers.
That's no more curious than this:
(let ((g (lambda (v)
(let ((f (lambda ()
;;(display "invoking f:") (display v) (newline)
v)))
(f)))))
(list (g 1) (g 2)))
=> (1 2)
Here's an example of the *same* procedure, invoked twice on the same
argument, returning two different integers:
(let ((f (lambda (x) (x x))))
(let ((result1 (f call/cc)))
(if (procedure? result1) (result1 1))
(let ((result2 (f call/cc)))
(if (procedure? result2) (result2 2))
(list result1 result2))))
=> (1 2)
In addition to returning two different integers, the two invocations
of f also return two different procedures, for a total of four
different return values.
You can also make a single invocation of a procedure return several
different results that have distinguishable integer components:
(let ((x (lambda () (call/cc (lambda (k) (cons 1 k))))))
(let ((result (x)))
(let ((n (car result))
(k (cdr result)))
(cond ((= n 1) (k (cons 2 k)))
((= n 2) (k (cons 3 k)))
((= n 3) 'we-are-having-fun-yet)))))
=> we-are-having-fun-yet
By the way, if you (Holm) eschew call/cc but add what's known as
call/ec, or call-with-escaping-continuation, then you don't get nearly
the headaches of call/cc. Call/ec creates a procedure similar to the
one created by call/cc, but it signals an error if it is invoked after
the captured continuation or any of its ancestor continuations have
been used. Call/ec functionality is not all that extraordinary, and
can be found in languages as mundane as C (in which it goes by the
name setjmp/longjmp).
It sounds like the call/cc that you have implemented only works
reliably in call/ec situations. If you're not up to truly
implementing call/cc, then I think it would be a better idea for you
to just implement call/ec and signal erroneous uses of it, rather than
to get people's hopes up by providing something called call/cc but
then warning that using it breaks your implementation of lexical
environments.
-al
| |
| Nils M Holm 2005-04-11, 4:02 pm |
| Al-Qaeda Petrofsky <al-qaeda@petrofsky.org> wrote:
> Here's an example of the *same* procedure, invoked twice on the same
> argument, returning two different integers:
>
> (let ((f (lambda (x) (x x))))
> (let ((result1 (f call/cc)))
> (if (procedure? result1) (result1 1))
> (let ((result2 (f call/cc)))
> (if (procedure? result2) (result2 2))
> (list result1 result2))))
> => (1 2)
>
> In addition to returning two different integers, the two invocations
> of f also return two different procedures, for a total of four
> different return values.
What do here is use (lambda (x) (x x)) to construct two different
instances of the same function (a function that binds its argument
to a name) and then use this function to bind the value 1 to result1
and the value 2 to result2.
To me your program does not seem to do anything more interesting than
(let ((f (lambda (y) (lambda (x) x))))
(let ((result1 (f 0)))
(let ((result1 (result1 1)))
(let ((result2 (f 0)))
(let ((result2 (result2 2)))
(list result1 result2))))))
=> '(1 2)
I still see no implementation of
(cons (f 0) (f 0)) => '(1 2)
using just the procedures mentioned in <d35h51$hgt$1@online.de>
plus call/cc.
> By the way, if you (Holm) eschew call/cc but add what's known as
> call/ec, or call-with-escaping-continuation, then you don't get nearly
> the headaches of call/cc. [...]
Ah, but call/ec is not particularly interesting, and I like the headaches.
> It sounds like the call/cc that you have implemented only works
> reliably in call/ec situations. [...]
My implementation of call/cc works reliably in many situations
(including the programs in your recent posting). Finally, keep
in mind that ArrowLISP is not Scheme. No, I am not taking the
easy way out here, my goal definitely /is/ to make ArrowLISP's
call/cc behave as close as possible to Scheme's call/cc. I am
just taking a break.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Szavai Gyula Gabor 2005-04-11, 4:02 pm |
| On Sat, 9 Apr 2005, Nils M Holm wrote:
> szgyg@ludens.elte.hu wrote:
>
> Please see my reply to Antons posting.
> True, but
>
> ((f 0) x) = ((f 0) x)
>
> which indicates to me that both (f 0)s are (different instances of)
> the same function - much in the same way as '(x y z) and '(x y z) are
> different instances of the same list. I would consider them equal,
> even if they are not eq?.
OK. You identify functions/programs with their results, and ignore the
execution's process.
>
> I would say that you cannot express mutation by application.
> (And not even by application plus call/cc.)
>
> Proofs to the contrary are welcome.
>
> You can, however, use a purely applicative language L to write
> an interpreter that implements L plus mutation. This interpreter
> would interpret a language other than L, though.
>
> Turing-completeness does not imply that things are implemented
> easily.
Because lambda-calculi is Turing-complete, you can write a purely
applicative program, for _any_ program, which produces identical result.
That and the above mean: SIDE EFFECT DOES NOT EXIST.
Best regards
szgyg
--
Side effect? What's that? Use Haskell!
| |
| Nils M Holm 2005-04-11, 4:02 pm |
| Szavai Gyula Gabor <szgyg@elte.hu> wrote:
> Because lambda-calculi is Turing-complete, you can write a purely
> applicative program, for _any_ program, which produces identical result.
> That and the above mean: SIDE EFFECT DOES NOT EXIST.
Early FORTRAN did not allow recursive procedures (subroutines).
Early FORTRAN was Turing-complete.
Does this imply, in your opinion, that recursive procedures do not exist?
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Matthias Blume 2005-04-11, 8:59 pm |
| Nils M Holm <nmh@despammed.com> writes:
> Al-Qaeda Petrofsky <al-qaeda@petrofsky.org> wrote:
>
> What do here is use (lambda (x) (x x)) to construct two different
> instances of the same function (a function that binds its argument
> to a name) and then use this function to bind the value 1 to result1
> and the value 2 to result2.
>
> To me your program does not seem to do anything more interesting than
>
> (let ((f (lambda (y) (lambda (x) x))))
> (let ((result1 (f 0)))
> (let ((result1 (result1 1)))
> (let ((result2 (f 0)))
> (let ((result2 (result2 2)))
> (list result1 result2))))))
> => '(1 2)
To me it does do something far more interesting. See below.
> I still see no implementation of
>
> (cons (f 0) (f 0)) => '(1 2)
At least the following is possible:
Let G be purely functional (it uses only COND, CAR, CDR, PROCEDURE?,
numeric literals, and ordinary function application), and F be
"almost" purely functional (it uses only CALL/CC and LAMBDA). We can
craft particular G and F such that
(let ((c (cons (f) (f))))
(g c)
c)
evaluates to (1 . 2).
In other words, the only difference between straight (cons (f) (f))
and this is that the result of CONS will be passed to another purely
functional function G before eventually being returned.
Would that satisfy your curiosity?
If so, here is the implementation:
(define (g x)
(cond ((procedure? (car x)) ((car x) 1))
((procedure? (cdr x)) ((cdr x) 2))
(else '())))
(define (f) (call-with-current-continuation (lambda (k) k)))
Matthias
| |
| Alpha Beta Petrofsky 2005-04-11, 8:59 pm |
| Nils M Holm <nmh@despammed.com> wrote:
> my intuition still tells me that call/cc cannot introduce side
> effects in purely applicative programs.
> ... observable side effect in a purely applicative program would be
> a function f that delivers different values when passed the same
> actual argument multiple times
I responded:
You replied:
[color=darkred]
> To me your program does not seem to do anything more interesting
> than [ an uninteresting expression ]
Hmmm, ... perhaps it would clarify things if you list which of the
following points are the ones with which you disagree:
1. During the above expression's evaluation, only one binding is
created for a variable named F, and this binding holds the same
procedure at all times.
2. The procedure F is invoked twice.
3. Each invocation of F returns twice.
4. At one point, an invocation of F returns 1.
5. At another point, the other invocation of F returns 2.
6. Both invocations of F pass to it the same argument: call/cc.
7. This is therefore an example of "a function f that delivers
different values when passed the same actual argument multiple
times".
8. This is interesting.
-al
P.S. Please note that the accepted meaning of "A => B" in
comp.lang.scheme is, as in r5rs, that "expression A evaluates to value
B" and not "expression A and expression B evaluate to the same value"
(see r5rs section 1.3.4 for a more precise specification). Hence,
some examples of correct usage are:
(+ 1 2) => 3
(list 1 2) => (1 2)
''(1 2) => '(1 2)
(car '(foo)) => foo
and some examples of incorrect usage are:
(+ 1 2) => (- 4 1)
(list 1 2) => '(1 2)
''(1 2) => ''(1 2)
(car '(foo)) => 'foo
P.P.S. Please note that when I say "the accepted meaning of A in
comp.lang.scheme is B", I mean that B is the meaning of A accepted by
some set C of comp.lang.scheme readers. C is guaranteed to contain I,
but the size of C - I may vary.
| |
| Jim Blandy 2005-04-11, 8:59 pm |
|
Alan Bawden has shown that call/cc gives you state. Here is a
function that returns a "cell" that holds a value you can get or set,
implemented using only purely functional operations, and call/cc.
(define (make-cell)
(call-with-current-continuation
(lambda (return-from-make-cell)
(letrec ((state
(call-with-current-continuation
(lambda (return-new-state)
(return-from-make-cell
(lambda (op)
(case op
((set)
(lambda (value)
(call-with-current-continuation
(lambda (return-from-access)
(return-new-state
(list value return-from-access))))))
((get) (car state)))))))))
((cadr state) 'done)))))
(define (set-cell cell value) ((cell 'set) value))
(define (ref-cell cell) (cell 'get))
I found this at:
http://zurich.csail.mit.edu/piperma...ary/001216.html
Sorry if someone's already posted this.
| |
| Abdulaziz Ghuloum 2005-04-12, 3:59 am |
| Jim Blandy wrote:
> Alan Bawden has shown that call/cc gives you state. Here is a
> function that returns a "cell" that holds a value you can get or set,
> implemented using only purely functional operations, and call/cc.
It's not the call/cc that's giving you state in this example--it's the
letrec. Call/cc is used to expose the set! embedded in the r5rs
compliant letrec. This example will not work if your letrec is some
form of fix, Y, or poor-man's letrec (I don't know if this term is
popular outside of IU).
Aziz,,,
| |
| Nils M Holm 2005-04-13, 8:57 am |
|
Alpha Beta Petrofsky <alpha-beta@petrofsky.org> wrote:
I had thought of a similar program before and had come to the conclusion
that
(let ((f (call/cc call/cc)))
(cond ((procedure? f) (f 'foo))
(#t f)))
does roughly the same as
(letrec ((f (lambda (x)
(cond ((procedure? x) (f 'foo))
(#t x)))))
(f (lambda (x) x)))
and hence though that it was not particularly interesting: both programs
re-start a computation with different arguments.
However...
[color=darkred]
> 1. During the above expression's evaluation, only one binding is
> created for a variable named F, and this binding holds the same
> procedure at all times.
> 2. The procedure F is invoked twice.
> 3. Each invocation of F returns twice.
> 4. At one point, an invocation of F returns 1.
> 5. At another point, the other invocation of F returns 2.
> 6. Both invocations of F pass to it the same argument: call/cc.
> 7. This is therefore an example of "a function f that delivers
> different values when passed the same actual argument multiple
> times".
> 8. This is interesting.
After taking a second glance at your program, I agree to your points 1..8.
So call/cc does indeed cause an observable side effect.
Thank you for the example.
> P.S. Please note that the accepted meaning of "A => B" in
> comp.lang.scheme is, as in r5rs, that "expression A evaluates to value
> B" and not "expression A and expression B evaluate to the same value"
Agreed.
> (see r5rs section 1.3.4 for a more precise specification). Hence,
> some examples of correct usage are:
>
> (+ 1 2) => 3
Agreed.
> (list 1 2) => (1 2)
> ''(1 2) => '(1 2)
> (car '(foo)) => foo
See below.
> and some examples of incorrect usage are:
>
> (+ 1 2) => (- 4 1)
Agreed.
> (list 1 2) => '(1 2)
> ''(1 2) => ''(1 2)
> (car '(foo)) => 'foo
(list 1 2) => (1 2)
suspiciously reads as: the application of LIST to 1 and 2 reduces to
the application of 1 to 2, while
(list 1 2) => '(1 2)
unambigously says that the application of LIST to 1 and 2 reduces to
a list containing the elements 1 and 2.
Hence I prefer the latter version over the former. Similar reasons
apply to foo vs 'foo.
> P.P.S. Please note that when I say "the accepted meaning of A in
> comp.lang.scheme is B", I mean that B is the meaning of A accepted by
> some set C of comp.lang.scheme readers. C is guaranteed to contain I,
> but the size of C - I may vary.
It seems that, for some cases, I am part of the complement of C.
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Nils M Holm 2005-04-13, 8:57 am |
|
Matthias Blume <find@my.address.elsewhere> wrote:
> Let G be purely functional (it uses only COND, CAR, CDR, PROCEDURE?,
> numeric literals, and ordinary function application), and F be
> "almost" purely functional (it uses only CALL/CC and LAMBDA). We can
> craft particular G and F such that
>
> (let ((c (cons (f) (f))))
> (g c)
> c)
>
> evaluates to (1 . 2).
>
> [...]
>
> Would that satisfy your curiosity?
Yes, it does. Thanks for the explanation.
So would it be fair to say that call/cc does cause side effects, but
cannot be used to add mutable state to a function? Eg, would you agree
that
(cons (f 0) (f 0)) => (1 . 2)
cannot be implemented in this straight form using just
COND, CAR, CDR, PROCEDURE?, LAMBDA, and CALL/CC?
Nils
--
Nils M Holm <nmh@despammed.com> http://www.holm-und-jeschag.de/nils/
Symbolic Computing - an Introduction to Pure LISP: http://www.t3x.org/scipl/
| |
| Matthias Blume 2005-04-13, 4:00 pm |
| Nils M Holm <nmh@despammed.com> writes:
> Matthias Blume <find@my.address.elsewhere> wrote:
>
> Yes, it does. Thanks for the explanation.
>
> So would it be fair to say that call/cc does cause side effects, but
> cannot be used to add mutable state to a function? Eg, would you agree
> that
>
> (cons (f 0) (f 0)) => (1 . 2)
>
> cannot be implemented in this straight form using just
> COND, CAR, CDR, PROCEDURE?, LAMBDA, and CALL/CC?
Yes.
|
|
|
|
|