This is the mail archive of the
guile@sources.redhat.com
mailing list for the Guile project.
Re: CTAX revisited
- To: Ian Bicking <ianb at colorstudy dot com>
- Subject: Re: CTAX revisited
- From: Marius Vollmer <mvo at zagadka dot ping dot de>
- Date: 23 Jul 2000 23:39:40 +0200
- Cc: guile at sourceware dot cygnus dot com
- References: <20000723131320.F285@lothlorien>
[ Ahem. ;) ]
Ian Bicking <ianb@colorstudy.com> writes:
> Okay, well not quite CTAX. But, in an effort to revitalize (or
> maybe just vitalize) translation, I'm writing a translator from a
> C-like syntax to Scheme (no semantic translation at all).
That's a good idea. However, I would say that you do attempt semantic
translation when allowing things like `return', `break', `continue'
and--not to forget--`goto'.
As you say, using call/cc would be easiest and I think call/cc is
intended exactly for this purpose. However, getting around its
performance problems in Guile might be worthwhile and there are some
more or less involved ways I can think of.
Maybe it should be mentioned that the first step should probably be to
use call/cc regardless and see whether it really _has_ the percieved
performance problems. Because call/cc is only used behind the scenes
in translated code, people can start to use the translator even if
performance is not optimal. (That's another reason why not targeting
TCL right away is a good thing: people would compare the translator to
the original TCL implementation and when our performance sucks, that
would be a publicity disaster.)
When we do find that call/cc in Guile has inadequate performance, then
we can start optimizing its use, by ...
- Generating explicit continuation passing code
Because there is a mechanical translator involved, that translator
could emit continuation-passing-style code (CPS). With such a
style, call/cc is not needed.
However, I would expect CPS code to be slower than regular code and
it is likely harder for a Scheme compiler to produce good code for
CPS code when it doesn't expect it. Further, requiring all
translators to emit CPS code could be a put-off for potential
translator writers.
- Optimizing call/cc itself
Maybe the innards of the Guile evaluator could be mended to improve
the performance of call/cc.
However, I don't know what would be involved precisely. Surely the
integration ease of C code would suffer.
- Not using call/cc but something more specialized
`goto' (which is what suffice as a primitive to implement the rest
of `break', `continue') and `return' do not need the full power of
call/cc. For `goto', tail-calls are sufficient, and for `return',
something like `call/ec' (call with escaping continuation) would be
enough and can be implemented more efficiently.
An escaping continuation is a continuation that is guaranteed to be
invoked only once and only so that call frames are removed from the
stack.
The corresponding Common Lisp constructs are `tagbody' (for `goto')
and `block' (for `return').
I think it would be best to implement something like `tagbody' and
`block' in Guile and use it from the translators. Some more thoughts:
- Maybe we should merge the two concepts into one (`tagblock'?), or
maybe we shouldn't.
- A Schemey `tagbody' should probably put its tags in the single
lexical name space and instead of using `go', the tags are invoked
as functions.
- `block' could use `catch/throw'.
(The last two points are exemplified by the `while' macro in boot-9.)
- A compiler will probably treat `tagbody' and `block' as special
forms and be able to emit good code for them.
- As convenience, we might provide `with-return' which is a `block'
without a name.
As an example how I think `tagbody' and `with-return' would be used,
here is an example translation of a language I just made up:
first_even (l)
{
while (!null(l))
{
e = car(l);
if (!number (e))
break;
if (even (e))
return e;
l = cdr (l);
}
return false;
}
==>
;; first_even (l)
;; {
(define (first_even l)
(with-return
;; while (!null(l))
(tagbody
continue
(if (not (not (null? l)))
(break))
;; {
;; e = car (l);
(let ((e (car l)))
(if (not (number? e))
(break))
(if (even? e)
(return e))
(set! l (cdr l)))
;; }
(continue)
break)
;; return (false);
(return #f)))
;; }
Here is some working code to illustrate further:
;; (block LABEL FORMS...)
;;
;; Execute FORMS. Within FORMS, a lexical binding named LABEL is
;; visible that contains an escape function for the block. Calling
;; the function in LABEL with a single argument will immediatly stop
;; the execution of FORMS and return the argument as the value of the
;; block. If the function in LABEL is not invoked, the value of the
;; block is the value of the last form in FORMS.
(define-macro (block label . forms)
`(let ((body (lambda (,label) ,@forms))
(tag (gensym 'return-)))
(catch tag
(lambda () (body (lambda (val) (throw tag val))))
(lambda (tag val) val))))
;; (with-return FORMS...)
;;
;; Equivalent to (block return FORMS...)
(define-macro (with-return . forms)
`(block return ,@forms))
;; (tagbody TAGS-AND-FORMS...)
;;
;; TAGS-AND-FORMS is a list of either tags or forms. A TAG is a
;; symbol while a FORM is everything else. Normally, the FORMS are
;; executed sequentially. However, control can be transferred to the
;; forms following a TAG by invoking the tag as a function. That is,
;; within the FORMS, there is a lexical binding for each TAG with the
;; symbol hat is the tag as its name. The bindings carry functions
;; that will execute the FORMS following the respective TAG.
;;
;; The value of a tagbody is always `#f'.
(define (transform-tagbody forms)
(let ((start-tag (gensym 'start-))
(block-tag (gensym 'block-)))
(let loop ((cur-tag start-tag)
(cur-code '())
(tags-and-code '())
(forms forms))
(cond
((null? forms)
`(block ,block-tag
(letrec ,(reverse! (cons (list cur-tag `(lambda ()
,@(reverse!
(cons `(,block-tag #f)
cur-code))))
tags-and-code))
(,start-tag))))
((symbol? (car forms))
(loop (car forms)
'()
(cons (list cur-tag `(lambda ()
,@(reverse! (cons `(,(car forms))
cur-code))))
tags-and-code)
(cdr forms)))
(else
(loop cur-tag
(cons (car forms) cur-code)
tags-and-code
(cdr forms)))))))
(define-macro (tagbody . forms)
(transform-tagbody forms))
;; first_even (l)
;; {
(define (first_even l)
(with-return
;; while (!null(l))
(tagbody
continue
(if (not (not (null? l)))
(break))
;; {
;; var e = car (l);
(let ((e (car l)))
(if (not (number? e))
(break))
(if (even? e)
(return e))
(set! l (cdr l)))
;; }
(continue)
break)
;; return (false);
(return #f)))
;; }
[ Hey, that was fun! ]