Hi Alex,

> BTW, those who advocate lexical binding are suspiciously silent when it
> comes to demonstrations of the power of dynamic binding.
>
> For example, I'm still waiting for lexical-bound Common Lisp or Scheme
> solutions in
>
>    http://rosettacode.org/wiki/First_class_environments

Maybe because nobody has written it yet?  :-)

Ok, I'll face your challenge!  Here are my solutions in Common Lisp.

1st try:

(let ((envs (loop for i from 1 to 12 collect (list i 0))))
  (do ()
      ((not (some (lambda (e) (apply (lambda (n cnt) (< 1 n)) e)) envs)))
    (mapc (lambda (e)
            (symbol-macrolet ((n (car e))
                              (cnt (cadr e)))
              (format t "~4d" n)
              (unless (= 1 n)
                (incf cnt)
                (setq n (if (= 1 (logand 1 n))
                            (1+ (* n 3))
                            (/ n 2))))))
          envs)
    (terpri))
  (dotimes (i 48) (write-char #\=))
  (terpri)
  (mapc (lambda (e) (apply (lambda (n cnt) (format t "~4d" cnt)) e)) envs)
  (terpri))

There are three cases where you use 'job' in your PicoLisp solution.
The first and last don't need first class environments at all, simply
passing the values down the call stack is enough because the values are
only being read.  The second case is where these values are being
modified and only this case "needs" "first class environment".

I don't think this assignment has much to do with the question of
lexical versus dynamic bindings and even not with built-in support for
first class environment.  There are a few solutions in languages that
don't have that support and they simply create a structure and work with
that.

In Common Lisp, 'job' can be implemented as a macro rather easily:

(defmacro job (env args &body body)
  (let ((x (gensym)))
    `(let ((,x ,env))
       (symbol-macrolet (,@(mapcar (lambda (y) `(,y (cdr (assoc ',y ,x)))) 
args))
         ,@body))))

(let ((envs (loop for i from 1 to 12 collect (list (cons 'n i) (cons 'cnt 0)))))
  (do ()
      ((not (some (lambda (e) (job e (n) (< 1 n))) envs)))
    (mapc (lambda (e)
            (job e (n cnt)
              (format t "~4d" n)
              (unless (= 1 n)
                (incf cnt)
                (setq n (if (= 1 (logand 1 n))
                            (1+ (* n 3))
                            (/ n 2))))))
          envs)
    (terpri))
  (dotimes (i 48) (write-char #\=))
  (terpri)
  (mapc (lambda (e) (job e (cnt) (format t "~4d" cnt))) envs)
  (terpri))

I actually prefer the following version:

(defmacro job (args &body body)
  `(lambda (env)
     (symbol-macrolet (,@(mapcar (lambda (x) `(,x (cdr (assoc ',x env)))) args))
       ,@body)))

(let ((envs (loop for i from 1 to 12 collect (list (cons 'n i) (cons 'cnt 0)))))
  (do ()
      ((not (some (job (n) (< 1 n)) envs)))
    (mapc (job (n cnt)
            (format t "~4d" n)
            (unless (= 1 n)
              (incf cnt)
              (setq n (if (= 1 (logand 1 n))
                          (1+ (* n 3))
                          (/ n 2)))))
          envs)
    (terpri))
  (dotimes (i 48) (write-char #\=))
  (terpri)
  (mapc (job (cnt) (format t "~4d" cnt)) envs)
  (terpri))

How would my last 'job' macro look like as a fexpr in PicoLisp so that
you can write "(job ...)" instead of "'((E) (job E ...))" if you were to
use 'mapc instead of 'for' fexpr?

BTW Common Lisp _embraces_ dynamic binding because that's the right
thing to use in many cases.

However, as usually happens, bigger power in one direction limits the
power in other directions.  I can think of two other examples:

1) Control flow: continuations vs stack based discipline vs finite state
   machines.  In this case, lots of things can be proved about a FSM and
   they are very static and predictable.  On the other side of the
   spectrum are continuations, which are impossible to reason about and
   don't compose.

2) Evaluation: FEXPRs vs macros vs functions.

The more powerful abstraction one chooses, the less one can reason about
the code.

So what lexical binding brings is that by limiting the expressive power
for some variables, one can reason about many more things.  For example,
one can optimize or automatically infer closures.

I am inclined to think that fexprs are not a good thing, because like
first class continuations, they break compose-ability (or whatever is
the english word for that).

That brings the question of how much of PicoLisp really needs fexprs?  I
think I could implement most of PicoLisp in Common Lisp rather easily
using functions and macros without the need for fexprs at all.  Even in
case of PicoLisp, most of the things are actually not fexprs.  It's just
that everything is implemented using FEXPRs under the hood in PicoLisp.

Cheers,

Tomas

-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to