# concatenative lexically-scoped polymorphic mutable variables

## John Nowak — 2008-07-18 07:54:30

    Recently, I had been working on a problem in 5th. Because 5th is a

    linear language, it is impossible for any object to be referenced more

    than once (by definition). One problem this creates, amongst many, is

    that global variables cannot be efficiently implemented. The reason is

    that accessing a global variable either requires that it be copied,

    which may be expensive, or requires temporarily removing it, which is

    unsafe as an attempt to fetch it again before it is restored will

    cause an error. Neither is acceptable.

    One way of solving this problem is to allow global variables to be

    removed, but to also keep track of this on the type level. This is

    implemented by passing an extensible record on top of the stack (or on

    the side of the stack -- whichever sounds nicer to you). A "push"

    function can be used to push an object into a particular "slot" in the

    record provided that the slot is currently empty. A "pull" function

    can be used to remove an object from a slot provided that the slot is

    currently full. These slots are polymorphic in the sense that objects

    of different types can inhabit the same slot at different times

    throughout the program.

    If this is taken to its logical conclusion by allowing slots to hold

    multiple values, and by adding a bit of type system magic to ensure

    that only the most recently bound object in a slot can be manipulated

    until the point of the introduction of that pseudo-binding returns

    (which is doable), you end up with a type-safe form of dynamic

    scoping. This is not particularly interesting as I believe it is

    already well-known that dynamic scoping is compatible with

    concatenativity. (It may, however, be interesting that this is

    relatively easy to handle in terms of type inference.)

    What is perhaps a new realization is that this approach gets you

    lexical scoping as well. This is doable by generating unique names for

    the lexical pseudo-variables in a particular definition. Because the

    names are unique, other functions will be unable to access the slots.

    5th's disallowing of recursive definitions is critical here as well as

    it prevents the slots from getting clobbered before the they are

    removed and discarded. Since the types of the slots are carried

    individually in the type system, mutating these slots can be done in a

    manner that is type-safe, even if the type associated with a

    particular slot changes within a definition.

    In a non-linear variant of 5th, we could employ the same system but

    disallow updating or removing values from slots. This would give us

    variables that work as if they were implemented via substitution.

    However, substitution is not actually necessary as the fetching of a

    "variable" can be delayed until the function that fetches an object

    from a particular slot is called. Because substitution is avoided, the

    language remains a concatenative (albeit with rather fancy namespace

    control). The big bonus here is that you get a dual view of the

    semantics; you can look at it either from the perspective of term

    rewriting and substitution or via the perspective of function

    composition. This has led me to consider dropping linearity as this is

    just too pretty.

    There are a few restrictions on all this. As already indicated, the

    language must not allow recursion. (Actually, tail recursion is

    allowable.) Additionally, the language must not have first class

    functions as the pseudo-variables cannot be closed over. Finally,

    special care must be taken for things like callback functions. In

    particular, the type system must ensure that the function given does

    not reference any slots meant to be used to emulate lexical scoping.

    This is straightforward to enforce.

    This email is really about 10 pages shorter than it should be. If

    anyone managed to follow along, or would like clarification, I'd be

    happy to respond.

    - John

## John Cowan — 2008-07-18 15:45:16

    John Nowak scripsit:

     > There are a few restrictions on all this. As already indicated, the

    > language must not allow recursion. (Actually, tail recursion is

    > allowable.) Additionally, the language must not have first class

    > functions as the pseudo-variables cannot be closed over. Finally,

    > special care must be taken for things like callback functions. In

    > particular, the type system must ensure that the function given does

    > not reference any slots meant to be used to emulate lexical scoping.

     What you've done is reinvent Fortran 66, which has exactly this model

    and uses a purely static store.  It doesn't even need a stack except

    to hold return addresses, and CPS conversion (if it had been known

    at the time) could have disposed of that.

    So your pseudo-variables can be implemented using plain old global

    variables with no problems.

    --

    John Cowan   cowan@...    http://ccil.org/~cowan

    I am he that buries his friends alive and drowns them and draws them

    alive again from the water. I came from the end of a bag, but no bag

    went over me.  I am the friend of bears and the guest of eagles. I am

    Ringwinner and Luckwearer; and I am Barrel-rider.  --Bilbo to Smaug

## John Nowak — 2008-07-18 21:35:20

    On Jul 18, 2008, at 11:45 AM, John Cowan wrote:

     > What you've done is reinvent Fortran 66,

     Hah! Well, glad I'm making progress then...

     > So your pseudo-variables can be implemented using plain old global

    > variables with no problems.

     Aye, I had realized that at least. Good to know that I was right in my

    thinking, even if it be thinking that's hardly new.

    Thanks John.

    - Other John