This is the mail archive of the guile@sources.redhat.com mailing list for the Guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: CTAX revisited


[ 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! ]

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]