From Newsgroup: comp.lang.forth
A couple of years ago, I noticed that itrCOs possible to implement
Lisp-style dynamic scoping in standard Forth in one line of code:
: (let!) dup @ over swap 2r> rot >r rot >r >r >r ! ; : let! (let!) 2r> ! ;
It turns out the implementation works perfectly (within its limits) in
all four Forth implementations I could test it in, including F83 from
01984.
ItrCOs tricky and not very efficient, though.
Background on lexical and dynamic scoping -----------------------------------------
I realized that some readers may not know what rCLdynamic scopingrCY is, so
I thought I should include a background section for those readers.
rCLDynamic scopingrCY is a peculiar construct, mostly abandoned in current programming languages, which gives you rCLlocal variablesrCY in an unusual
way. It was invented accidentally for the first Lisp interpreter in
01959.
With dynamic scoping, if a subroutine called, say, rCLMenifeerCY has a local variable named rCLCantosrCY, for example as a named argument, this locality
is typically implemented as follows:
1. Upon entry to Menifee, the existing value of Cantos, if any, is saved
on a stack.
2. Upon exit from Menifee, the saved value is popped from the stack and
Cantos is set to it, overwriting any values that may have been
assigned to Cantos inside Menifee.
This is closely analogous to how CPU general-purpose registers are saved
and restored in machine code on subroutine call and return; the
implementation technique is called rCLshallow bindingrCY.
For most purposes, this works just like the rCLlexicalrCY kind of local-variable scoping that werCOre used to from languages like C, Rust,
and PL/1, but if Menifee calls some other subroutine, call it
rCLYugoslaviarCY, and Yugoslavia reads the variable Cantos, instead of
seeing the global value of Cantos (if any), it will see MenifeerCOs local value.
Emacs Lisp is one of the few programming languages that still supports
dynamic scoping (PostScript being another), and even elisp is starting
to default to the more efficient and predictable lexical scoping. But,
given these definitions:
(defvar Cantos "53" "Example variable for dynamic scoping demo")
(defun Yugoslavia () (insert Cantos))
(defun Menifee (Cantos) (Yugoslavia))
evaluating the Emacs-Lisp form `(Menifee "72")` will insert rCL72rCY into
your current buffer, not rCL53rCY, because the function parameter Cantos is bound to the argument "72" that is passed using dynamic scoping.
In a few cases, the dynamic-scoping behavior is more desirable:
- In Forth, for example, itrCOs fairly common to want to set `base` to
some value temporarily, so that words like `.` will print out values in
base 10 or base 16 or whatever you want.
- In graphics code, itrCOs common to want to set the pen color or current
font to some value temporarily.
- In Emacs Lisp, searching commands like `search-forward` are
case-sensitive or not depending on the value of the Boolean variable
`case-fold-search`, so if you want to do a case-insensitive search,
you can establish a local dynamic binding with
(let ((case-fold-search nil))
(search-forward ...))
- In Emacs Lisp, setting the variable `deactivate-mark` to `t`
deactivates the mark after returning to the main event loop. Various
kinds of Emacs Lisp functions that modify the buffer implicitly set
it, so you can establishing a local dynamic bind to *prevent* this
with
(let ((deactivate-mark "irrelevant"))
...)
- Common Lisp is statically scoped by default but also supports
dynamically-scoped rCLspecial variablesrCY, which are useful for things
like redirecting `*standard-output*` to a string, as
`with-output-to-string` does:
* (with-output-to-string (*standard-output*) (prin1 5) (prin1 3))
"53"
Van der HorstrCOs `co` operator
-----------------------------
In <
https://home.hccnet.nl/a.w.m.van.der.horst/forthlecture6.html> Van
der Horst implements stackless coroutines in Forth by swapping the top
two items on the return stack, so that its callerrCOs caller will return
to the point in its caller that called `co`, assuming they arenrCOt using
the return stack for anything else:
: co 2r> >r >r ;
This is very similar in its effect to GolangrCOs `defer`, so it occurred
to me that you could use it to restore saved variable values.
Hacking the return stack to implement dynamic scoping in Forth --------------------------------------------------------------
The ideal user interface would be a word, maybe called something like
`let!`, which saves the value and location of a variable on the return
stack, sets the variable to a new value, and arranges for its caller to
return into value-restoring code when that caller returns. This would
allow you to, for example, write GForthrCOs `dec.` word as follows:
decimal : dec. 10 base let! . ;
The desired stack effect for `let!` in this case is something like
( newval a-addr -- ) R: ( -- a-addr oldval let!+m dec.+n )
We can implement this as follows:
: (let!) dup @ over swap 2r> rot >r rot >r >r >r ! ; : let! (let!) 2r> ! ;
This single-line definition does seem to work when I test it in Gforth,
PForth and PFE. In F83 it requires a definition of `2r>`. After some
flubs, including crashing DOSBox, this worked:
: 2r> r> r> r> rot >r swap ;
### Walkthrough of the stack effects ###
This is pretty confusing, and it involves precisely the kind of tricky
stack manipulation you should really never do, so hererCOs a play-by-play. After `dup @ over`, we have changed the operand stack from
newval a-addr
to
newval a-addr oldval a-addr
Then with `swap 2r>` we swap oldval and a-addr and get two levels of
return addresses onto the operand stack:
newval a-addr a-addr oldval dec.+n let!+m
Now with `rot >r rot >r` we push oldval and a-addr onto the return
stack, leaving
newval a-addr dec.+n let!+m
Then we push the return addresses back onto the return stack with `>r >r`rCerCorCebut, crucially, they are now in the reverse order, just as when `co` executed `2r> >r >r`. That leaves our operand stack with just
newval a-addr
And so, at last, `(let!)` invokes `!` and sets the variable to the
requested local value.
And then it returns. But, critically, it doesnrCOt return to `let!`! It returns directly to the callsite where `dec.` or whatever called `let!`, without first executing the `2r> !` after the callsite of `(let!)` in
`let!`, which I've denoted as `let!+m` in the above. ItrCOs when `dec.`
(or whatever the caller of `let!` is) returns that we finish executing
!`, which loads oldval and a-addr onto the operand stack and then
uses `!` to restore the variable's old value.
The dynamically-scoped Towers of Hanoi
--------------------------------------
variable src variable dest variable stor variable n
defer move-disc
: text-disc
cr ." Move disc " n @ . ." from " src @ emit ." to " dest @ emit ;
' text-disc is move-disc
: hanoi ( src stor dest n -- )
n let! dest let! stor let! src let!
n @ 0= if exit then
src @ dest @ stor @ n @ 1- recurse
move-disc
stor @ src @ dest @ n @ 1- recurse ;
char A char B char C 4 hanoi
(I used `n @ .` because for some reason PForth doesnrCOt implement `?`.)
That seems to work just as you would hope in Gforth, PForth, PFE, and
even F83 (except that F83 requires `ascii` for `char`). IrCOm told it
even works in Christopher LeonardrCOs <
https://github.com/veltas/zenv>, a
ZX Spectrum Forth! (But only up to 3 discs, because 4 would require 65
items on the return stack.)
A blockfile implementation of the above usable with F83 and GForth is at <
http://canonical.org/~kragen/sw/dev3/hanoi.blk>.
Harmony and dissonance with Forth
---------------------------------
The Hanoi example demonstrates that this form of rCLlocal variablesrCY doesnrCOt impede you from factoring out individual lines of code that use
the variables. Block-scoped lexical local variables would, which has
often been a justification for not implementing local variables in
Forths, or for not using themrCerCorCevariables that are lexically subroutine-local would need to be explicitly passed as parameters, while variables shared between the two subroutines can provide implicit
dataflow.
Of course, while implicit dataflow can be very flexible, it also makes
your code harder to debug and understand.
Reflections on Forth
--------------------
This is the kind of thing that gets people excited about Forth: it's
such a malleable language that you can add fundamental facilities like dynamically-scoped local variables to it in a single line of code.
Such things can be an attractive nuisance. This implementation isnrCOt
very efficient; in an interpreted Forth (without superinstructions) it requires, I think, 16 subroutine invocations per local variable. A
native-code compiled Forth will require something like that number of instructions instead, but your return-address branch predictor will
explode, so your performance will still go to hell. And such things are
pretty confusing to debug when they go wrongrCerCorCe`(let!)` has a sequence
of nine stack manipulations in a row, most of them return-stack
manipulations.
And Forth tends to break easily. In Gforth you *can* invoke `let!` from
the text interpreter usefully:
3 x let! x ? 3 ok
x ? 0 ok
but this behavior is not guaranteed. Running `3 x (let!)` crashes
Gforth. `Let!` doesnrCOt work inside a `do loop`, either:
: (let!) dup @ over swap 2r> rot >r rot >r >r >r ! ; : let! (let!) 2r> ! ; ok
variable x : xsum 0 do x @ i + x let! loop x @ ; ok
5 xsum .
:3: Return stack overflow
5 >>>xsum<<< .
Backtrace:
If you wanted to implement dynamic scoping in Forth in an efficient way, yourCOd want to statically allocate space in a stack frame for all the variables a colon definition created local bindings for, copy the old
values of those variables into that stack frame on entry, and copy them
out on exit. This would add about two instructions to a call and return sequence for a definition using this facility, plus two instructions per variable. And it would break return-stack manipulations like this one.
A related problem is that Forth tends to disproportionately attract people
who like to spend their time hacking on the language implementation
rather than using it to write code to do something elserCerCorCeboth
because you *can* hack on the implementation so easily, and because you
have to understand the implementation in order to debug your failures.
This can sink projects in Forth.
*****
The above is a lightly edited copy of forth-dynamic-scoping.md from <
http://canonical.org/~kragen/sw/pavnotes2.git/>. Commentary is eagerly welcomed.
Kragen
--- Synchronet 3.22a-Linux NewsLink 1.2