Co-author of the thesis here - we wrote it almost 6 years ago, so my memory may be a little rusty :-)

The question we dealt with was how to compile a weakly, implicitly and dynamically typed language (see the definitions in the thesis, but basically a language where the variable types cannot be statically determined in the general case and will be coerced if the run-time type does not match operator requirements) in a manner that is more efficient than simply interpreting the program source code.

I do not recall seeing any related work with regards to BASIC and Lisp at the time, however, we may very well have overlooked something. Thank you for the references!

Lisp is strongly, implicit and dynamically typed, with type coercions. For example it provides generic arithmetic:

    * (let ((a 1)              ; integer
            (b 2.0)            ; default float
            (c 1/3)            ; ratio
            (d #c(1.2 2.3)))   ; complex number
        (+ a b c d))
    #C(4.5333333 2.3)

Variables A, B, C, D have no type declarations. The values usually carry type information. The + operation will take any numeric value and create a result value of a type it chooses. for example (+ 1/2 1/2) will result to 1. Adding ratios might create a ratio or an integer.

There is a whole bunch of literature on compiling Scheme:

https://github.com/scheme-live/library.readscheme.org/blob/m...

Thanks for the link - a lot of interesting literature to dig into!

Generally with unknown (at compile-time) variable types, you need to box the variables (carry type information in addition to the value). The operators may then either work on the boxed variables and choose behaviour based on the type information or the operators may be specialized in many versions to work on the unboxed variables (this requires the run-time to dispatch to the correct specialized version, if the types cannot be determined statically).

This is generally a trade-off between space and execution time - if the number of possible types are low (either because of a limited type system or because the possible different types can be determined statically), then it may make sense to specialize.

In JS, in addition to mutable types and values for each variable, you also have a challenge with variable scope. It is possible to introduce new variables in the global scope from a local scope, so depending on run-time values, a variable for a given statement may or may not have been declared.

An example from the thesis:

  function f(){
    a = 5;
  }

  function g(){
    console.log(a); 
  }

  if(x){
    f();
  }

  g();

Assuming that 'a' was not declared elsewhere also, the call to 'g()' will either print out the value of 'a' (ie. "5") or will result in a run-time error.

> you need to box the variables (carry type information in addition to the value).

Dealing with boxing/unboxing and trying to minimize boxing operations in computations is regularly done in Lisp compilers.

> It is possible to introduce new variables in the global scope from a local scope

just like in Lisp. Generally Javascript and Lisp have a lot in common. Scoping rules are different though and Lisp is not object-oriented at the core - but provides closures or adds object-oriented extensions like CLOS which are semi-optional.

  * (defun f ()
      (setf a 5))
  ; in: DEFUN F
  ;     (SETF A 5)
  ; ==>
  ;   (SETQ A 5)
  ; 
  ; caught WARNING:
  ;   undefined variable: COMMON-LISP-USER::A
  ; 
  ; compilation unit finished
  ;   Undefined variable:
  ;     A
  ;   caught 1 WARNING condition
  F


  * (defun g ()
      (print a))
  ; in: DEFUN G
  ;     (PRINT A)
  ; 
  ; caught WARNING:
  ;   undefined variable: COMMON-LISP-USER::A
  ; 
  ; compilation unit finished
  ;   Undefined variable:
  ;     A
  ;   caught 1 WARNING condition

As you can see the compiler warns about undefined variables, but deals with it.

  * (if (> (random 1.0) 0.5) (f))
  5
  * (g)

  5 
  5

If we remove the binding of A, then we get a runtime error.

  * (makunbound 'a)
  A
  * (g)

  debugger invoked on a UNBOUND-VARIABLE in thread
  #<THREAD "main thread" RUNNING {10005205B3}>:
    The variable A is unbound.

  Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

  restarts (invokable by number or by possibly-abbreviated name):
    0: [CONTINUE   ] Retry using A.
    1: [USE-VALUE  ] Use specified value.
    2: [STORE-VALUE] Set specified value and use it.
    3: [ABORT      ] Exit debugger, returning to top level.

  (G)
     source: (PRINT A)
  0] 

As one can see, both F and G are actually compiled machine code functions. Both functions we directly AOT compiled to machine code when I entered them at the prompt.

  * (disassemble #'f)
  ; disassembly for F
  ; Size: 38 bytes. Origin: #x226D3C9C
  ; 9C:       498B4540         MOV RAX, [R13+64]                ; no-arg-parsing entry point
                                                                ; thread.binding-stack-pointer
  ; A0:       488945F8         MOV [RBP-8], RAX
  ; A4:       488B15A5FFFFFF   MOV RDX, [RIP-91]                ; 'A
  ; AB:       BF0A000000       MOV EDI, 10
  ; B0:       B904000000       MOV ECX, 4
  ; B5:       FF7508           PUSH QWORD PTR [RBP+8]
  ; B8:       B898914F22       MOV EAX, #x224F9198              ; #<FDEFN SET>
  ; BD:       FFE0             JMP RAX
  ; BF:       0F0B0F           BREAK 15                         ; Invalid argument count trap
  NIL
  * (disassemble #'g)
  ; disassembly for G
  ; Size: 57 bytes. Origin: #x226D3D3C
  ; 3C:       498B4540         MOV RAX, [R13+64]                ; no-arg-parsing entry point
                                                                ; thread.binding-stack-pointer
  ; 40:       488945F8         MOV [RBP-8], RAX
  ; 44:       488B05A5FFFFFF   MOV RAX, [RIP-91]                ; 'A
  ; 4B:       8B50F5           MOV EDX, [RAX-11]
  ; 4E:       4A8B142A         MOV RDX, [RDX+R13]
  ; 52:       83FA61           CMP EDX, 97
  ; 55:       480F4450F9       CMOVEQ RDX, [RAX-7]
  ; 5A:       83FA51           CMP EDX, 81
  ; 5D:       7412             JEQ L0
  ; 5F:       B902000000       MOV ECX, 2
  ; 64:       FF7508           PUSH QWORD PTR [RBP+8]
  ; 67:       B838555422       MOV EAX, #x22545538              ; #<FDEFN PRINT>
  ; 6C:       FFE0             JMP RAX
  ; 6E:       0F0B0F           BREAK 15                         ; Invalid argument count trap
  ; 71: L0:   0F0B17           BREAK 23                         ; UNBOUND-SYMBOL-ERROR
  ; 74:       00               BYTE #X00                        ; RAX
  NIL

Turbo Basic (nowadays PowerBasic), Quick Basic, VAX Basic, Amos, CBASIC, VB 6.0, PureBasic, REALbasic (nowadays Xojo) are all examples from BASIC compilers released between late 70's and late 90's.

...in a manner that is more efficient than simply interpreting the program source code.

By which I guess you mean abstract interpretation[0]? Not specifically the linked to RATA system but using it for type checking in general.

Haven't read the thesis yet but am kind of interested in the subject matter so will check it out in the morning over coffee.

[0] https://link.springer.com/chapter/10.1007%2F978-3-642-11970-...