What is a programming language with dynamic scope and static typing?

Question

I know the language exists, but I can't put my finger on it.

dynamic scope and static typing?

Answer 1

Dynamic scope means, that the variable and its type in a specific line of your code depends on the functions, called before. This means, you can not know the type in a specific line of your code, because you can not know, which code has been executed before.

Static typing means, that you have to know the type in every line of your code, before the code starts to run.

This is irreconcilable.

Answer 2

I haven't found elsewhere has it written down, but AXIOM CAS (and various forks, including FriCAS which is still been actively developed) uses a script language called SPAD with both a very novel strong static dependent type system and dynamic scoping (although it is possibly an unintended implementation bug).

Most of the time the user won't realize that, but when they start trying to build closures like other functional languages it reveals its dynamic scoping nature:

                       FriCAS Computer Algebra System 
                         Version: FriCAS 2021-03-06
                   Timestamp: Mon May 17 10:43:08 CST 2021
-----------------------------------------------------------------------------
   Issue )copyright to view copyright notices.
   Issue )summary for a summary of useful system commands.
   Issue )quit to leave FriCAS and return to shell.
-----------------------------------------------------------------------------
 

(1) -> foo (x,y) == x + y
                                                                   Type: Void
(2) -> foo (1,2)
   Compiling function foo with type (PositiveInteger, PositiveInteger)
       -> PositiveInteger 

   (2)  3
                                                        Type: PositiveInteger
(3) -> foo             

   (3)  foo (x, y) == x + y
                                                    Type: FunctionCalled(foo)
(4) -> bar x y == x + y
                                                                   Type: Void
(5) -> bar  

   (5)  bar x == y +-> x + y
                                                    Type: FunctionCalled(bar)
(6) -> (bar 1)
   Compiling function bar with type PositiveInteger -> 
      AnonymousFunction 

   (6)  y +-> #1 + y
                                                      Type: AnonymousFunction
(7) -> ((bar 1) 2)

   (7)  #1 + 2
                                                    Type: Polynomial(Integer)

Such a behavior is similar to what will happen when trying to build a closure by using (lambda (x) (lambda (y) (+ x y))) in a dynamically scoped Lisp, such as Emacs Lisp. Actually the underlying representation of functions is essentially the same as Lisp in the early days since AXIOM has been first developed on top of an early Lisp implementation on IBM mainframe.

I believe it is however a defect (like what JMC happened did when implementing the first version of LISP language) because the implementor made the parser to do uncurrying as in the function definition of bar, but it is unlikely to be useful without the ability to build the closure in the language.

It is also worth notice that SPAD automatically renames the variables in anomalous functions to avoid captures so its dynamic scoping could be used as a feature as in other Lisps.

Answer 3

We can try to reason about what such a language might look like. Obviously something like this (using a C-like syntax for demonstration purposes) cannot be allowed, or at least not with the obvious meaning:

int x_plus_(int y) {
    return x + y;        // requires that x have type int
}

int three_plus_(int y) {
    double x = 3.0;
    return x_plus_(y);   // calls x_plus_ when x has type double
}

So, how to avoid this?

I can think of a few approaches offhand:

1. Commenters above mention that Fortran pre-'77 had this behavior. That worked because a variable's name determined its type; a function like x_plus_ above would be illegal, because x could never have an integer type. (And likewise one like three_plus_, for that matter, because y would have the same restriction.) Integer variables had to have names beginning with i, j, k, l, m, or n.

2. Perl uses syntax to distinguish a few broad categories of variables, namely scalars vs. arrays (regular arrays) vs. hashes (associative arrays). Variables belonging to the different categories can have the exact same name, because the syntax distinguishes which one is meant. For example, the expression foo $foo, $foo[0], $foo{'foo'} involves the function foo, the scalar $foo, the array @foo ($foo[0] being the first element of @foo), and the hash %foo ($foo{'foo'} being the value in %foo corresponding to the key 'foo'). Now, to be quite clear, Perl is not statically typed, because there are many different scalar types, and these are types not distinguished syntactically. (In particular: all references are scalars, even references to functions or arrays or hashes. So if you use the syntax to dereference a reference to an array, Perl has to check at runtime to see if the value really is an array-reference.) But this same approach could be used for a bona fide type system, especially if the type system were a very simple one. With that approach, the x_plus_ method would be using an x of type int, and would completely ignore the x declared by three_plus_. (Instead, it would use an x of type int that had to be provided from whatever scope called three_plus_.) This could either require some type annotations not included above, or it could use some form of type inference.

3. A function's signature could indicate the non-local variables it uses, and their expected types. In the above example, x_plus_ would have the signature "takes one argument of type int; uses a calling-scope x of type int; returns a value of type int". Then, just like how a function that calls x_plus_ would have to pass in an argument of type int, it would also have to provide a variable named x of type int — either by declaring it itself, or by inheriting that part of the type-signature (since calling x_plus_ is equivalent to using an x of type int) and propagating this requirement up to its callers. With this approach, the three_plus_ function above would be illegal, because it would violate the signature of the x_plus_ method it invokes — just the same as if it tried to pass a double as its argument.

4. The above could just have "undefined behavior"; the compiler wouldn't have to explicitly detect and reject it, but the spec wouldn't impose any particular requirements on how it had to handle it. It would be the responsibility of programmers to ensure that they never invoke a function with incorrectly-typed non-local variables.

Your professor was presumably thinking of #1, since pre-'77 Fortran was an actual real-world language with this property. But the other approaches are interesting to think about. :-)