call/cc use cases?
m_l...@yahoo.com
with good use cases.
In particular, I want to see a use case where the escape procedure is
called multiple times.
Is it correct that call/cc is an analog of the C++ try{}catch(){} ?
wmfarr
call/cc is actually *much* more powerful than C++ try-catch. Here's
how I think of it, with a couple of examples of use (from my own
work). As you'll quickly realize, I'm not an academic computer
scientist---so this explanation may be a bit basic, but I'll let the
actual academics fill in any gaps.
The Basics
==========
In the evaluation of a Scheme program, each statement has a "future"
which is "everything which will happen once this statement is
evaluated". For example, in
(+ 1 (+ 2 3))
the statement (+ 2 3) has a "future" which looks like (+ 1 XXXX),
where XXXX is filling in for the eventual result of (+ 2 3). Since
the result of every computation (forgetting for a moment about
(values ...)) is a single value, we could write the future as a
function parameterized over the return value of (+ 2 3): the "future"
of (+ 2 3) is
(lambda (value) (+ 1 value))
The call/cc procedure constructs such a function explicitly. In a
sense, call/cc "tags" a return point, in the following sense:
(+ 1 (call/cc
(lambda (return-to-+-1)
(return-to-+-1 7)
(+ 2 3))))
will evaluate to (+ 1 7) => 8. The (+ 2 3) never gets evaluated
because we have instead supplied 7 to the continuation (+ 1 XXXXX).
The real power of continuations comes from the fact that we don't have
to "use" the return-point right away. Consider the following example:
(begin
(define return-to-print-1-+ #f)
(printf "The sum is ~a~%"
(+ 1 (call/cc
(lambda (ret)
(set! return-to-print-1-+ ret)
(+ 2 3)))))
(return-to-print-1-+ 7))
Try it. It should print "The sum is 6" and then "The sum is 8". The
second printing occurs because the call to return-to-print-1-+ with an
argument of 7 jumps back to the point XXX in
(printf "The sum is ~a~%"
(+ 1 XXX))
with XXX given a value of 7.
It's very common to see the combination of call/cc and set! above.
There's another way to accomplish the same thing without using set! by
employing "delimited continuations" using prompt, shift, control,
etc., but I don't know much about that. I'll let the academics
explain more about it.
Examples
========
See http://wmfarr.blogspot.com/2006/08/one-more-example-of-python-generators.html
for an example of using continuations to implement generators (as in
python, where calling (yield XXX) will suspend the current
computation, and return XXX to the caller).
Here's an example I was working on just yesterday. The context is
that I have an iterative procedure for trying to solve multi-
dimensional non-linear equations. The procedure iterates a maximum of
max-iter times. If it iterates too many times without finding a
solution, it raises an exception which includes a continue/iter
procedure which will continue the computation for an additional number
of iterations. This is a particularly useful compromise between
letting the computation run forever (not a good idea in case it's gone
haywire), and forcing termination after max-iter steps: the user gets
to examine the state of the procedure, and decide whether to keep
going or abandon the computation. (In that sense, it's a bit like
common lisp's exception system, but I digress....) Here's the code:
(define-struct (exn:multi-solve:max-iter exn)
(iter best-guess continue/iter) #f)
(define (multi-solve F converged? max-iter)
(let ((dF/dx (jacobian F)))
(lambda (v)
(let loop ((v v) (i 0) (max-iter max-iter))
(cond
((>= i max-iter)
(let ((new-iter (call/cc
(lambda (restart)
(raise (make-exn:multi-solve:max-iter
"maximum iterations exceeded
in multi-solve"
(current-continuation-marks)
i
v
restart))))))
(loop v 0 (if (>= new-iter 0) new-iter 0))))
((converged? v) v)
(else
(let ((F (vector->f64vector (F v)))
(dF/dx (deriv-jac->matrix (dF/dx v))))
(let ((dx (matrix-solve dF/dx (f64vector-scale F -1))))
(loop (vector-add v (f64vector->vector dx)) (add1 i)
max-iter)))))))))
There's a lot of extraneous code there, but the part you're interested
in is:
(let ((new-iter (call/cc
(lambda (restart)
(raise (make-exn:multi-solve:max-iter
"maximum iterations exceeded
in multi-solve"
(current-continuation-marks)
i
v
restart))))))
(loop v 0 (if (>= new-iter 0) new-iter 0))
This stores the restart procedure into the exception which is raised,
temporarily aborting the computation. If the exception handler
decides to re-enter the computation, it calls (restart N), which
returns N to the position XXX in
(let ((new-iter XXX))
(loop v 0 (if (>= new-iter 0) new-iter 0))
I hope this helps! If I had more time, I would show you how to
implement try/catch using call/cc---it's a fun exercise.
Will
m_l...@yahoo.com
> to "use" the return-point right away. Consider the following example:
> (begin
> (define return-to-print-1-+ #f)
>
> (printf "The sum is ~a~%"
> (+ 1 (call/cc
> (lambda (ret)
> (set! return-to-print-1-+ ret)
> (+ 2 3)))))
>
> (return-to-print-1-+ 7))
>
> Try it. It should print "The sum is 6" and then "The sum is 8".
If fact, it gave me an endless loop.
But I managed to write something working:
; return 2^n : 2^n >= x
(define powerof2
(lambda (x)
(define again ())
(define result 0)
(set! result
(* 2
(call/cc
(lambda (to-iterate)
(set! again to-iterate)
1
) ) ))
(if (< result x)
(again result)
result
)) )
It works:
stklos> (powerof2 5)
8
stklos> (powerof2 4)
4
stklos> (powerof2 1000000)
1048576
stklos> (powerof2 60000)
65536
but what I dislile about this code is extensive use of variables:
two auxiliary variables get set!
Can it be rewritten without veriables?
And what do values do?
stklos> (values 1 2 3)
1
2
3
stklos> (+ (values 1 2 3))
1
2
3
stklos> (+ 1 (values 1 2 3))
2
?
m_l...@yahoo.com
> See http://wmfarr.blogspot.com/2006/08/one-more-example-of-python-generators.html
> for an example of using continuations to implement generators (as in
> python, where calling (yield XXX) will suspend the current
> computation, and return XXX to the caller).
Gosh!
They use all this *syntax stuff that I do not understand!
How do all these syntax define-syntax with-syntax etc work?
Nils M Holm
> How do all these syntax define-syntax with-syntax etc work?
http://www.t3x.org/sketchy/vol1/sl17.html
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
m_l...@yahoo.com
able to understand what it does.
So what does (values ) do?
; return 2^n : 2^n >= x
(define powerof2
(lambda (x)
(define while<x
(lambda (z)
(if (< (car z) x)
((cdr z) z)
(car z)
) ))
(while<x
( (lambda (x y)
(cons (* x (car y)) (cdr y)
) )
2
(call/cc
(lambda (to-iterate)
(cons 1 to-iterate)
)) ) ) ))
stklos> (powerof2 0)
2
stklos> (powerof2 4)
4
stklos> (powerof2 30000)
32768
To get it even less readable, I could remove the remaining (define )
replacing (while<x ) by the lambda-expression... Is there something
like
readability rules for Scheme? (like "don't use ?: at all" in C[++]/
Java)?
wmfarr
> If fact, it gave me an endless loop.
This is probably the result of a different REPL context---I was using
MzScheme, not stklos. What i mean is that the code which takes the
result of evaluating your input and prints it, and then waits for new
input is part of the "future" when you capture the continuation.
Depending on exactly what your implementation does there, you may or
may not wind up with an infinite loop when you jump back (I think it
depends on whether the implementation treats each statement
separately, or compiles them in a bunch, but I'm not really sure.)
Yeah, that was the reason for the other call/cc-based operators like
prompt, control, shift, etc. You could check out the sequence of PLT
Scheme Blog posts starting at http://blog.plt-scheme.org/2007/07/callcc-and-self-modifying-code.html
, which discuss exactly your objection above, and go from there.
> Can it be rewritten without veriables?
> And what do values do?
>
> stklos> (values 1 2 3)
> 1
> 2
> 3
> stklos> (+ (values 1 2 3))
> 1
> 2
> 3
> stklos> (+ 1 (values 1 2 3))
> 2
>
> ?
(values 1 2 3) returns a "multiple value" object. The only guaranteed
correct way to use it is in
(call-with-values (lambda () (values 1 2 3)) +) => 6
If you need to return more than one value from a function (say a
numerical approximation which should return its best-guess and the
estimated error on that guess), it's usually a more efficient and
clean way than choosing an arbitrary container to stick these in.
(The idea in the standard was that compliers could stick the values
directly in registers exactly where the receiving function would want
to find them, for no extra cost or allocation.)
It looks above as if stklos is doing weird things with multiple values
in a single-value context above, which can be a bit confusing. The
first (the one where (values 1 2 3) prints 1, then 2, then 3) can be
explained because the REPL probably works like
(call-with-values (lambda () (eval (read))) print)
So it becomes (print 1 2 3), which is what you see.
The second (where (+ (values 1 2 3)) prints 1, then 2, then 3) occurs
because single-argument + is the identity function, so the values
object just passes right through to print, and we get the same result
as before. (A more cautious implementation would probably throw an
error here because (+ (values ...)) expects only one value, not many,
but stklos doesn't.)
The last one (where (+ 1 (values 1 2 3)) => 2) can be explained by
saying that stklos ignores more than one value when values are used in
a single-value context, so this is like writing (+ 1 1). Again, a
more cautious implementation would throw an error here because only
one value is expected here, but you're giving + three values in its
second argument.
Hope that helps!
Will
wmfarr
> > Seehttp://wmfarr.blogspot.com/2006/08/one-more-example-of-python-generat...
> > for an example of using continuations to implement generators (as in
> > python, where calling (yield XXX) will suspend the current
> > computation, and return XXX to the caller).
>
> Gosh!
>
> They use all this *syntax stuff that I do not understand!
>
> How do all these syntax define-syntax with-syntax etc work?
Really quickly (syntax-case is a big, complicated topic), all the
define syntax stuff is a code-re-writing system. It takes an input
pattern, in this case
(define-generator (name arg ...) body0 body1 ...)
and turns it into
(define (name arg ...)
(letrec ((continue-k #f)
(return-k #f)
(yield
(lambda args
(let/cc cont
(set! continue-k cont)
(call-with-values
(lambda () (apply values args))
return-k)))))
(lambda ()
(let/cc ret
(set! return-k ret)
(if continue-k
(continue-k '())
(begin
body0 body1 ...
(error 'name "reached end of generator values")))))))
The with-syntax in the middle is to introduce the identifier 'yield
into the output in the same lexical context as the original body.
This is necessary because the code re-writer keeps track of which
symbols 1) appear in the code at the re-writing site and 2) appear in
the define-syntax expression at the defining site. In case 1),
identifiers refer to the lexical environment around the re-writing
site, and in case 2) identifiers refer to the lexical environment at
the defining site. This property is called hygiene, if you want to
read more about it.
I expect that users of the macro is going to have a (yield some-value)
expression in their body, and I want to define the value of 'yield's
binding for them (so that (yield some-value) returns some-value to the
caller). But, if I just put 'yield in the output of the macro, it
will refer to 'yield in *my* environment, not the yield that comes in
as input---even though the symbols are the same, they will refer to
different bindings because of syntax. The with-syntax call says "make
the syntax object _yield_ refer to the identifier 'yield in the same
lexical context as the body0 input expression". That way, the 'yield
in the letrec and any yield in the body refer to the same binding, and
I can arrange for the macro user that (yield some-value some-other-
value ...) does the right thing.
Hope that helps.
Will
m_l...@yahoo.com
> m_l...@yahoo.com wrote:
> > How do all these syntax define-syntax with-syntax etc work?
>
> http://www.t3x.org/sketchy/vol1/sl17.html
Thanks!
By the way, the definition of case given at the link is different from
the standard case
(I reformatted the text a bit, so that the matching paren is always
either in
the same line or in the same column).
Namely, in the worst case it evaluates key as many times as there are
branches, while
the standard case evaluates it only once.
Is it possible to define a syntax rule so that key is evaluated only
once,
and no identifier conflict is possible?
(define-syntax mcase
(syntax-rules (else)
( (_ key (else expr ...))
(begin expr ...)
)
( (_ key (data expr ...))
(if (memv key 'data)
(begin expr ...)
(if #f #f)
) )
( (_ key (data expr . exprs)
more-cases ...
)
(if (memv key 'data)
(begin expr . exprs)
(mcase key more-cases ...)
) ) ) )
(define my1 (lambda() (display "my1\n")1))
stklos> (mcase (my1) ((2 3) 1) ((4) 2) ((5 6) 3)(else 4))
my1
my1
my1
4
stklos> (case (my1) ((2 3) 1) ((4) 2) ((5 6) 3)(else 4))
my1
4
m_l...@yahoo.com
**** Error:
%execute: variable `let/cc' unbound
Is it possible to define let/cc in terms of other functions?
Or maybe re-write (let/cc stuff) as (call/cc other-stuff)?
wmfarr
> Is it possible to define a syntax rule so that key is evaluated only
> once,
> and no identifier conflict is possible?
>
Yep. Here it is, based on mcase:
(define-syntax mcase
(syntax-rules (else)
((_ key (else expr ...))
(begin expr ...))
((_ key (data expr ...))
(if (memv key 'data)
(begin expr ...)
(if #f #f)))
((_ key-expr (data expr . exprs)
more-cases ...)
(let ((key key-expr))
(if (memv key 'data)
(begin expr . exprs)
(mcase key more-cases ...))))))
Doing this sort of thing is good practice whenever you have an
"expression-type" pattern variable. The basic rule is: expression
type pattern variables should never appear more than once in the
output pattern, and, unless you really need to do otherwise, you
should evaluate those expressions in the order given.
(By the way, if you're worried about all the extra (let ...) blocks
introduced in the above recursive expansion of mcase, don't. A simple
copy-propagation step in a compiler will eliminate all but the first.
See, for example,
http://www.google.com/url?sa=t&ct=res&cd=2&url=http%3A%2F%2Fwww.cs.indiana.edu%2F~chaynes%2Fdanfest%2Fdyb.pdf&ei=i8jmRs-xFI6meu3m8JEK&usg=AFQjCNGuj5pwDp3Qdi9pf3nWV5TXL39UcA&sig2=_0sRp8UuhkgKeuF5GVclgw
.)
Will
wmfarr
(define-syntax let/cc
(syntax-rules ()
((let/cc cont body1 body2 ...)
(call/cc
(lambda (cont)
body1 body2 ...)))))
Just like you could define-syntax let as a lambda application:
(define-syntax let
(syntax-rules ()
((let ((var-id1 expr1)
...)
body1 body2 ...)
((lambda (var-id1 ...)
body1 body2 ...)
expr1 ...))))
Fun!
Will
Nils M Holm
> On Sep 11, 5:36 pm, Nils M Holm <before-2007-10...@online.de> wrote:
> > http://www.t3x.org/sketchy/vol1/sl17.html
>
> Thanks!
>
> By the way, the definition of case given at the link is different from
> the standard case
> (I reformatted the text a bit, so that the matching paren is always
> either in
> the same line or in the same column).
> Namely, in the worst case it evaluates key as many times as there are
> branches, while
> the standard case evaluates it only once.
Good point. Will fix this in the next revision.
> Is it possible to define a syntax rule so that key is evaluated only
> once,
Sure. Note that the following definition is a hack, because it
allows CASE to be applied to three arguments. You might use
a helper function to prevent this.
(define-syntax case
(syntax-rules (else)
((_ #f key (else expr ...))
(begin expr ...))
((_ #f key (data expr ...))
(if (memv key 'data)
(begin expr ...)
(if #f #f)))
((_ #f key (data expr . exprs)
more-cases ...)
(if (memv key 'data)
(begin expr . exprs)
(case #f key more-cases ...)))
((_ key . clauses)
(let ((k key))
(case #f k . clauses)))))
> and no identifier conflict is possible?
There will not be any conflicts because of macros are "hygienic".
This means that variables in bindings introduced by SYNTAX-RULES
will have unique names:
(expand '(case (+ 1 2) ((3) 3)))
=> ((lambda (#{k |<n9?%sgtL-Jad\\%|})
(if (memv #{k |<n9?%sgtL-Jad\\%|} '(3))
3
(if #f #f (#3%void))))
(+ 1 2))
Nils M Holm
> Sure. Note that the following definition is a hack, because it
> allows CASE to be applied to three arguments. You might use
> a helper function to prevent this.
This should have been, of course:
Sure. Note that the following definition is a hack, because it
allows CASE to be applied to two keys when the first one is #F.
[...]
Doing so would make the macro ignore the first key and restore
the old behavior where keys are evaluated multiple times.
Sigh. Never write articles when in a hurry.
> (define-syntax case
> (syntax-rules (else)
> ((_ #f key (else expr ...))
> (begin expr ...))
> ((_ #f key (data expr ...))
> (if (memv key 'data)
> (begin expr ...)
> (if #f #f)))
> ((_ #f key (data expr . exprs)
> more-cases ...)
> (if (memv key 'data)
> (begin expr . exprs)
> (case #f key more-cases ...)))
> ((_ key . clauses)
> (let ((k key))
> (case #f k . clauses)))))
--