History of T (2001) | Hacker News Reader

History of T (2001)

paulgraham.com

117 pointstosh38 comments

Being an extremely young programmer (I'm 35), I had never quite understood what "dynamic scoping" is - the whole idea that scoping can somehow be done differently than "like in all the languages" was foreign to me until a few minutes ago. If you're an ignorant youth like me, here's some clarification.

Wikipedia's description is horrid, but C2's[0] is a gem:

"In dynamic scoping, by contrast, you search in the local function first, then you search in the function that called the local function, then you search in the function that called that function, and so on, up the call stack. "Dynamic" refers to change, in that the call stack can be different every time a given function is called, and so the function might hit different variables depending on where it is called from."

Sounds totally insane to me and I wonder how people made working software at all in the '80s. That said, I get happy when I remember that people often complain about how horrible it is that $OBSCURE_AWESOME_TECHNOLOGY never made it and how $TRENDY_FAD solves the same problem so much less elegantly. I mean, apparently an $AWESOME_TECHONOLOGY sometimes does win, against all odds - in this case lexical scoping. Yay Guy Steele!

http://wiki.c2.com/?DynamicScoping

EDIT: I just realized that shells copying all environment variables into child processes is basically a present-day example of dynamic scoping (although, fortunately, without mutation - we'd have entire data centers on fire if you could mutate parent process envs). It gives me a slightly better idea how this stuff could be used to make working software.

I'm comforted to know I'm still "extremely young" :-)

I think Bash is the only common-use language that uses dynamic scoping. Whenever you get into more than two functions everything can quickly become unmanageable if you don't prefix all your declarations with 'local'. Forget one of those, and the moment you reuse a variable name you'll find yourself with some annoying weird bugs.

You can get dynamic scoping in perl by prefixing things with `local`.

    $ENV{BLAH} = 'hi'; 
    $Some::Package::Var = 'there';

    {
      local $ENV{BLAH} = 'hello'; 
      local $Some::Package::Var = 'world';
      

      # this call will see 'hello' and 'world'
      some_method()
    }

    # this call will see 'hi' and 'there'
    some_method()

All the caveats with playing with globals above notwithstanding, it's more useful in practice as a way to get a 'slightly different copy of an object':

    my $a = { hello => 'world', other => 'stuff'};
    
    {
      delete local $a->{other};
      print "$a->{hello} $a->{other}\n";
    }
    
    print "$a->{hello} $a->{other}\n";

this gives

    world
    world stuff

Great way for setting up log contexts etc that automatically get removed after the scope exits...

With respect to the call stack, a dynamically scoped variable is like the dual of an exception. That is to say, an exception is a way for a method to communicate with methods that are above it in the call stack. And a dynamically scoped variable is a way for a method to communicate with methods below it in the call stack.

Of the two the dynamically scoped variable is more powerful than the exception because an exception can only propagate upwards. A dynamically scoped variable can propagate downward, upward, or sideways (ie sibling methods in the call graph can access the values that you placed into the dynamically scoped variable).

In terms of how much trouble you can get into by misusing it, the dynamically scoped variable is more problematic than the exception (all things being equal). A dynamically scoped variable is basically just a global variable that isn't quite 100% global. So you can get into all the same problems that a global can get you into with the added benefit (or sometimes problem) that any two instances of a dynamically scoped variable might actually be different because they are coming from a different caller.

Finally, there are some really good usages of a dynamically scoped variable. Consider reference counting. If you're doing reference counting every time you increase/decrease your reference count, you are going to need to modify a counter. This is fine if you only have one thread, but with multiple threads it means that every time you modifying the counter you'll need to lock. Not something you want to do if you're worried about speed. However, if you stuck your reference counting framework into dynamic variables that get populated in the thread spin up method, then you could guarantee that each reference counting instance is inside of it's own thread. Now you don't have to lock anymore when you modify the ref count (as long as you don't otherwise cross the thread barrier).

All in all, I suspect that it's better that we have lexical scoping as a standard. Most of the things that I want to do with dynamic scoping, I feel like should live in a language feature or library. Additionally, dynamic scoping is more likely to break other abstractions like object oriented programming (ie we can't think of the object as an encapsulated unit if the way that it functions is determined by the methods above it in the call stack).

These examples don't really do dynamic scoping justice, and there are a few inaccuracies here.

> A dynamically scoped variable can propagate downward, upward, or sideways (ie sibling methods in the call graph can access the values that you placed into the dynamically scoped variable).

The binding only propagates downwards, never sideways or upwards.

You can send values through bindings upwards, downwards, or sideways, but all you're doing is assigning a value to a memory location. This isn't particularly novel, because you can do the same thing with any other type of variable, or with fields in a structure, etc.

> A dynamically scoped variable is basically just a global variable that isn't quite 100% global. So you can get into all the same problems that a global can get you into with the added benefit (or sometimes problem) that any two instances of a dynamically scoped variable might actually be different because they are coming from a different caller.

This is no more a problem than it's a problem that when you call f(x), you might get a different value for x each time you call it, because x comes from the caller.

The common use cases for dynamic variables are certain seldom-changed parameters for functions and maintaining context. The basic reason for using them is to avoid having to pass a potentially large set of variables through a potentially large number of intermediate functions. Dynamic variables are most similar to thread-local variables.

For seldom-changed parameters, consider standard-output (asterisks and HN don't mix). It's common to want to redirect the output of some block of code to a different location, in a shell script you could do this very simply:

    {
      echo a
      echo b
    } >file.txt

In Lisp, you can do this by binding the standard-output variable:

    (with-open-file (stream "file.txt" :direction :output)
      (let ((*standard-output* stream))
        (print 'a)
        (print 'b)))

You can see that this isn't really some mysterious or dangerous phenomenon, it's a way to pass things down to functions without having to pass them as arguments. It's also commonly used for tracking the context of things like requests in a web server. In Haskell you'd do this by using a reader monad, and in Go you'd do this by adding entries a dictionary attached to your context.Context object.

This should be sufficient:

  (with-open-file (*standard-output* "file.txt" :direction :output)
    (print 'a)
    (print 'b))

I don't think dynamic scoping is a good idea, but I wanted to point out that it does have some advantages:

- Sometimes you actually do want to change one of a large number of parameters for the dynamic extent of a single function call without having to make all of them parameters to that function. Classic examples are turning logging on for a single function call, changing the pen color or clipping region for a call to a subroutine that draws some kind of graphic, and running a function with the output redirected to a memory buffer instead of stdout. Dynamic scoping works great for this. My .emacs.d/init.el has an example where I temporarily set the "deactivate-mark" variable to a true value while I invoke some search and replace functions which would normally deactivate the mark, and another example where I temporarily set the "case-fold-search" variable to a false value so that the searches invoked from there will be case-sensitive.

That said, PostScript solves this problem differently, using a graphics context stack and gsave/grestore operators to enable you to make local changes to that context. Languages that support exceptions for normal control flow (as opposed to aborting the job or whatever) need some kind of defer/RAII/context-manager approach to making sure you don't forget to call grestore during the exception unwinding.

- As the article explains, dynamic scoping can be more efficient, but it doesn't explain why. We usually read variables more frequently than we supply them with values as parameters. In a single-threaded environment, dynamic scoping allows you to compile a read of a variable as a load from the fixed memory location of that variable, even if it's a local variable, even if your functions are recursive. Static scoping, by contrast, requires you to compile reads of your local variables as indexed loads from a frame pointer which points at your function's activation record, again unless you forbid recursion. The indexed load involves an addition of a constant to a register to compute the address to fetch from, and until the 1980s this actually made your program run slower. (Nowadays it just makes your program toggle more transistors, since the addition can nearly always be computed in parallel with other operations, and it probably isn't a significant contribution to total power consumption.)

Carrying this logic to the extreme, Multics Emacs (and I think GNU Emacs as a spiritual descendant) would swap in the values of not only function-local variables in this way but all the buffer-local variables whenever you switched buffers. The logic was that Lisp code would read the variables considerably more often than you switched buffers, so it was worth making a buffer switch slower to make the Lisp code run faster.

(There's another way to implement dynamic scoping called "deep binding", but I don't know of real systems that used it.)

Dynamic binding originated as a bug in the Lisp interpreter — you'll note that it's in both McCarthy's original paper and the Lisp 1.5 metacircular interpreter — but the divergence of its semantics from the static-scoping semantics of the λ-calculus weren't appreciated until later.

Also, as a side note, it's pretty fucking sad that it's 2018 and we're still dealing with language implementations on a daily basis that do things like box all their fucking fixnums, incurring not only unnecessary inefficiency but also unnecessary memory allocation and nondeterminism, so that adding two small integers can throw an out-of-memory error or produce a timing information leak that reveals secret information to an attacker. CPython, I'm looking at you, you fucking piece of shit.

Dynamic scoping is useful for things that resemble shell I/O redirection, where you want to be able to refer to some resource in an indirect / implicit manner such that an actual resource can be injected at any time. For everything else it's just no good.

Dynamic scoping is about as impure as global variables. Even JS’ ES5 scoping is awful. Gimmie pure, single-static assignment with static compilation and strong, gradual typing any day of the week.

Dynamic scoping as default is considered a bad idea, but dynamic scope variables when they are requested and then clearly indicated are awesome idea. (Common Lisp uses muffs around dynamic variables as a convention).

In a sense, dynamic variables are global variables done right.

It helps to keep in mind that a lot of programmers at the time just didn't have deep callstacks - they had a language that did "subroutines" but not "functions", and formal notions of separating concerns were often unavailable in production environments. Scoping rules didn't matter a great deal because you were always pressed up against global scope, and coding conventions assumed that context(e.g. reusing temporary variables).

All of this was the kindling that made OOP light on fire in the 90's, as computing power raced ahead and the old practices could be questioned throughout mainstream computing. But truth be told, you can go really far with imperative/global scope and discipline. It just means that you're treating the computer as a rat's nest of wiring.

> Being an extremely young programmer (I'm 35)

Don't want to divert the conversation but in some of the circles I've been mingling lately, 35 in software engineering is 'get off my lawn' domain.

When I read that, I immediately failed safe and assumed a touch of sarcasm.

Mind you, I'm 47 and compared to some programmers I know of - I am still young (yay!) I reserve "get off my lawn" for those who still snigger about making doilies out of punch cards.

Sometimes (mainly in testing code), I've practically reinvented dynamic scoping: If you ever want to do "call function f(), but for this single call, redirect accesses of global.xyz to the value mockXyz instead", then what you're doing is essentially dynamic scoping. Sometimes it would have been better if f() just took xyz as an argument, but in some cases I can't help but think the dynamic-scoping-style solution is all-around simpler.

But I am so glad that dynamic scoping isn't the default scoping style for variables in sane languages.

A semi-modern example similar to shells, JSP includes also make variables dynamically scoped.

I often explain JavaScript's `this` in terms of dynamic scoping. Its value is determined by the code a function is called from, not where the function is defined.

I wonder how people made working software at all in the '80s

It seems to me a lot of the debate and handwringing about dynamic scoping happened in Lisp-world. I was a kid learning to program in the mid 80s and the high level languages I encountered - Pascal and C did not have dynamic scoping. I first heard of it in a Lisp context. It's not quite that exotic, though - lots of people have been exposed to Emacs Lisp and the Javascript 'this' weirdness, among others.

> Pascal and C did not have dynamic scoping

They also did not have first-class functions.

The Lisp community investigated dynamic scope, because functions can take functions as arguments and can return functions as values. In this context dynamic scope showed its problems and closures were wanted. It took some time to find out what the problems are and what solutions were: closures (first Lisp implementors tried to add closures as an additional programming construct) and then lexical scope by default. During some time there was also a difference between the Lisp interpreter (using dynamic scope) and the same language implemented with a compiler (using lexical scope). Scheme and then Common Lisp required that both use the same technique: lexical scope.

Since neither C nor PASCAL had first class functions, they never had the problems of implementing closures, implementing garbage collection, etc... This also means that users never were programming with closures in these languages.

They also did not have first-class functions.

Sure, for some values of 'did not'. What I'm getting at is (and I think, if I'm reading you right, so are you) this debate existed in a fairly specialized universe. There wasn't a time in the 80s where statistically anybody was grappling with the choice of lexical over dynamic scoping, at least, not for programs most people wrote or used. Block-structured languages were already the norm by then.

The dynamic binding 'debate' began in the Lisp community in the 60s. Some functional programming language designers and people thinking about implementing them also explored it then.

See: The Funarg problem, 1968 http://www.softwarepreservation.org/projects/LISP/MIT/Weizen...

Mid 70s Scheme then was the first dialect to use lexical binding as a default. From then on new dialects of Lisp or new versions of of it switched over time to lexical binding by default. Scheme names block-structured Algol as one of its influences. 1982 Common Lisp was initially described amd it was then also using lexical binding.

The primitive block structured languages like PASCAL had it from Algol, too. But it was not a big deal, because they had no Closures, were not using Interpreters, had first class functions, no higher-order functions, etc. Lisp users were looking to implement higher-order functions in a 'right' way.

But most Lisps never gave up to provide dynamic binding as a feature, since it is used in a lot of programs...

And even in the LISPs that did give up dynamic binding, you can still emulate it to some degree. E.g. in Scheme:

  (define-syntax fluid-let
    (syntax-rules ()
      ((_ () x . xs)
        (begin x . xs))
      ((_ ((v1 a1) (v2 a2) ...) x . xs)
        (let ((tmp v1))
          (set! v1 a1)
          (fluid-let ((v2 a2) ...)
            (let ((r (begin x . xs)))
              (set! v1 tmp)
              r))))))

  (define x 'foo)
  (define (f) x)

  (f) ==> foo

  (fluid-let ((x 'bar))
    (f))                ==>  bar

Dynamic scoping by default is a bit insane (although not as much as you may think), but optional dynamic scoping is amazing, as it can be used to customise behaviour within a call.

E.g. in Lisp one can do something like:

    (let ((*request* (make-request http-stuff))
          (*tracer* (make-tracer)))
      (set-up-response)
      (handle-request)
      (send-response))

And each of those functions will see the request object, as will each function those functions call, and so on down the call stack, without having to manually pass in a request object for each. And everything will see the tracer object, even functions whose callers have never even heard of tracing, even when those functions are in libraries which have never even heard of tracing.

If you're familiar with Go's contexts, this basically gives you a typesafe context for free.

Dynamic scoping is actually pretty awesome. I'm not a huge fan of it by default, but it's definitely a powerful capability to have as an option.

Even optional dynamic scoping can lead to some really strange bugs.

The better way to do something like your example is to make 'set-up-request' etc. methods of a class, along with their callees. Then instead of dynamically binding some variables, you instantiate your class with the desired values, and call the desired methods on the instance. You get pretty much the same elegance of expression, and no dynamic binding weirdness is required.

> The better way to do something like your example is to make 'set-up-request' etc. methods of a class, along with their callees. Then instead of dynamically binding some variables, you instantiate your class with the desired values, and call the desired methods on the instance. You get pretty much the same elegance of expression, and no dynamic binding weirdness is required.

That doesn't work, because functions called by functions called by functions called by set-up-request &c. won't see the values one wants them to see. The whole point of dynamic variables is that they transcend the stack.

Can this lead to really strange bugs? I don't really think so, but maybe. The whole point is that each function can customise the environment seen by the functions it calls. That's actually very clean.

> That doesn't work, because functions called by functions called by functions called by set-up-request &c. won't see the values one wants them to see.

They will if they're all methods of the class (as I said: "along with their callees"). And arguably, all the functions that care about these variables should be methods of a single class.

> Can this lead to really strange bugs? I don't really think so, but maybe.

In 1983 I was hacking on Symbolics Lisp Machines at Atari Cambridge Research. For reasons that need not concern us here, I created a package that did not import from LISP:, and made it the current package by setting the relevant special variable (whose name I can't show exactly here because HN will interpret the asterisks as indicating italics, thus: package). My Lisp Machine was no longer able to access its file server using the NFILE protocol, because this Lisp-Machine-specific protocol sent pieces of list structure across the wire, and along with the expected strings and integers, that list structure also sometimes contained instances of the symbol NIL. With the current package set to my package, the string "NIL" was treated by READ as a different symbol from LISP:NIL, breaking the protocol implementation.

I think that qualifies as a really strange bug.

Yes, the "process" (thread, in modern terminology) that handled the protocol should have had protective bindings of all the special variables that could influence its behavior. But somebody overlooked the current package as being one of them. If the reader had been an object one had to instantiate before calling, the bug would probably never have arisen (I expect there would have been a function STANDARD-READER, or some such, that one could call to get a reader instance with standard options).

> They will if they're all methods of the class (as I said: "along with their callees"). And arguably, all the functions that care about these variables should be methods of a single class.

I don't think so: the entire point is that functions in different libraries, written by different programmers, care about the same things — and this isn't a bad thing. E.g., if the user wants to customise his output language, then he wants to set it once; he doesn't want to have to set library.language for a dozen different libraries. And if for some reason he wants to generate a small piece of output in another language within one dynamic context, then he wants to set it only for that context, not just set it across all dynamic contexts (e.g. my menus should still display in English even if I'm running some stuff in Italian).

The difference in mindset between us, I think, is that maybe you think that a system is written by one person who can architect it such that he knows all the change points ahead of time; I'm thinking of large systems written by hundreds of people, in which that's just not possible. E.g. emacs or GNOME — heck, modern Microsoft Office would meet that definition.

Your example sounds like a weird pre-Common-Lisp thing. Nowadays that only way READ would read NIL as something different from COMMON-LISP:NIL would be if the current package didn't use COMMON-LISP — and surely that would be what one meant, if one did that (e.g. maybe one wanted to build a sandbox environment or something).

> But somebody overlooked the current package as being one of them. If the reader had been an object one had to instantiate before calling, the bug would probably never have arisen (I expect there would have been a function STANDARD-READER, or some such, that one could call to get a reader instance with standard options).

Such as WITH-STANDARD-IO-SYNTAX, perhaps? It does exactly what you're looking for.

The C2 description is of a possible implementation of dynamic scoping, not of dynamic scoping.

Dynamic scoping can work simply by saving and restoring a global variable (or a thread-local one, if need be). There is no need for a search through frames.

If there is an environment consisting of linked frames, they do not have to coincide with activation frames. They are frames in a dynamic environment. If a function doesn't bind anything in the dynamic environment, it doesn't contribute any new frame. So the dynamic environment can be considerably shallower than the call stack.

In the TXR Lisp, I maintain a global variable (a C variable) called dyn_env. It points to the top of the dynamic environment stack. A dynamic variable is bound by extending this stack. The old value dyn_env is saved on the run-time stack, and is restored later.

dyn_env is also part of the "extended_jmp_buf" context. This means that if a dynamic control transfer takes place (exception or other), dyn_env will be correctly restored to the value at the target site.

> so the function might hit different variables depending on where it is called from.

Not really. Well, look, if a function accesses an unbound variable, that can be diagnosed. The remaining question is whether a given dynamic variable being accessed (which we know exists due to the lack of any unbound variable diagnostics) is the global instance in the top-level environment, or a locally overridden one. That's what we don't necessarily know in a given function, and we are not supposed to care.

My mind was similarly blown when we went over dynamic scoping in a programming language concepts class. My mind was regularly blown by that class now that I think about it. If you ever get the chance to take something similar, I highly recommend it.

Lexical scoping is a function of space (lexical context) and dynamic scoping is a function of time. Consider:

  (let ((x 'lexical))
    (let ((f (lambda () x)))
      (let ((x 'dynamic))
        (f))))

In a lexically scoped system, X is bound to LEXICAL and then F is bound to a function returning X in the lexical context where X=LEXICAL. Then (another) X is bound to DYNAMIC and finally F is applied. The value that F returns is the value that X had in the lexical/spatial context of the definition of F.

In a dynamically scoped system, F is bound to a function that returns the value that X is currently bound to. Before the function is defined, X is bound to LEXICAL and later the same X is bound to a different value, DYNAMIC. The value returned by F is the value that X has at the time of the function application.

To try this in a dynamically scoped LISP, use may have to use

  (funcall f)

instead of (f) in the last line of the example.

In [0] the author uses dynamic scope (variables with dynamic scope are called special variable in common lisp) to help design a test system in common lisp.

Quoting the author: This is exactly the kind of problem dynamic variables were designed to solve.

Imagine that one of the test cases failed and you need to track down the problem. If you create a dynamic variable that each test function binds to the name of the function before calling check, then report-result can use it without check having to know anything about it.

I think that the main idea is that dynamic gives access to variables and functions defined in an upper level, something like creating classes and subclasses dynamically and they only live during a function evaluation.

[0] http://www.gigamonkeys.com/book/practical-building-a-unit-te...

You already realized that env vars are an example of dynamic scoping, and someone mentioned exceptions downthread.

But pretty much any serious programming language has some (often crappy ad-hoc) implementation of dynamic scoping somewhere, because it's very useful. Take decimal contexts in python -- would you really like to pass number of significant digits and rounding mode to every operation? Sadly, it's also an example of a crappy ad-hoc implementation (broken with async).

> Another implementation feat of T's was that it allowed interrupts between any two instructions of user code.

That was the goal, but the T3 compiler actually turned out to have a very subtle bug that manifested itself as the single hardest bug I have ever dealt with in my career. We used T to write research code for rovers and robotic arms at JPL. This code ran on two different machines: Sun3's running Solaris, and brandless embedded systems running vxWorks, but both running the same T compiler targeting the 68020 processor.

On the embedded systems we would get random crashes, but the same code running on Solaris ran flawlessly. Post-mortems revealed massive and random heap corruption, so the crash was manifesting itself long after the root cause. Because the problem was random an could not be reliably reproduced, it was impossible to find the root cause. And that is how matters stood for nearly a year until someone (I don't remember who, but it wasn't me) finally figured out how to reproduce the problem reliably. Then I spent a couple of days single-stepping through machine code until I finally found the problem: the stack pointer was being decremented while a live value was still on the stack. That value was accessed by the very next instruction. Those two instructions were simply out of order.

On Solaris this didn't matter because all the code ran in user space and was single-threaded. But vxWorks does not have a protected kernel address space. When an interrupt happens, that interrupt is processed on whatever process stack is currently active. So if you got an interrupt exactly between the stack pointer decrement and the subsequence load, the value was corrupted, and a few thousand instructions later everything would go kablooey.

I'm curious - what was the solution to the problem?

The solution was trivial: just reverse the two instructions in the code generator part of the compiler.

A couple of recent related discussions:

https://news.ycombinator.com/item?id=17716056

https://news.ycombinator.com/item?id=15054404

Stanford has/had a strong AI group, SAIL, that got passed around and now resides affiliated with GSB. When I was at SMI/BMIR, they had an old SAIL sign over in MSOB.

Anyone have more detail on Douglas W. Clark's GC? Ideally the cited article or a description of the algorithm.

Poor title.

Reply on news.ycombinator.com