scope - programming - Alcance estático(léxico) vs Alcance dinámico(Pseudocódigo)

pseudocode online

Question

Program A()
{
    x, y, z: integer;

    procedure B()
    {
        y: integer;
        y=0;
        x=z+1;
        z=y+2;
    }

    procedure C()
    {
        z: integer;

        procedure D()
        {
            x: integer;
            x = z + 1;
            y = x + 1;
            call B();
        }

        z = 5;
        call D();
    }

    x = 10;
    y = 11;
    z = 12;
    call C();
    print x, y, z;
}

Desde mi punto de vista, el resultado de este programa cuando se ejecuta usando scoping estático es: x = 13, y = 7, yz = 2.

Sin embargo, cuando se ejecuta usando un alcance dinámico , el resultado es: x = 10, y = 7 yz = 12.

Estos resultados son los que nuestro profesor nos dio. Sin embargo, no puedo entender por la vida de mí cómo ha llegado a estos resultados. ¿Podría alguien atravesar el pseudocódigo y explicar sus valores en los dos tipos diferentes de ámbitos?

Answer 1

Con el alcance estático (léxico) , la estructura del código fuente del programa determina a qué variables se refiere. Con alcance dinámico , el estado de tiempo de ejecución de la pila de programas determina a qué variable se refiere. Es probable que este concepto no sea muy familiar, ya que básicamente todos los lenguajes de programación de amplio uso en la actualidad (excepto tal vez emacs lisp) utilizan el alcance léxico, que suele ser mucho más fácil de razonar tanto para los humanos como para las herramientas de análisis.

Considere este programa de ejemplo mucho más simple (escrito en su sintaxis de pseudocódigo):

program a() {
  x: integer; // "x1" in discussions below
  x = 1;

  procedure b() {
    x = 2; // <-- which "x" do we write to?
  }

  procedure c() {
    x: integer; // "x2" in discussions below
    b();
  }

  c();
  print x;
}

El programa y el compilador se refieren a ambas variables como x , pero las he etiquetado como x1 y x2 para facilitar la discusión a continuación.

Con el alcance léxico, determinamos en tiempo de compilación a qué x nos estamos refiriendo en función de la estructura estática y léxica del código fuente del programa. La definición más interna de x en el alcance cuando se define b es x1 , por lo que la escritura en cuestión se resuelve en x1 , y ahí es donde x = 2 escribe, por lo que imprimimos 2 al ejecutar este programa.

Con el alcance dinámico, tenemos una pila de definiciones de variables rastreadas en el tiempo de ejecución, por lo tanto, a qué x escribimos depende de qué se trata exactamente del alcance y se ha definido dinámicamente en el tiempo de ejecución . Comenzando a ejecutar a empuja x => x1 en la pila, llamando c empuja x => x2 a la pila, y luego cuando llegamos a b , la parte superior de la pila es x => x2 , y entonces escribimos en x2 . Esto deja x1 intacto, por lo que imprimimos 1 al final del programa.

Además, considere este programa ligeramente diferente:

program a() {
  x: integer; // "x1" in discussions below
  x = 1;

  procedure b() {
    x = 2; // <-- which "x" do we write to?
  }

  procedure c() {
    x: integer; // "x2" in discussions below
    b();
  }

  c();
  b();
}

La nota b se llama dos veces, la primera vez a través de c , la segunda vez directamente. Con el alcance léxico, la explicación anterior no cambia y escribimos en x1 en ambas ocasiones. Sin embargo, con un alcance dinámico, depende de cómo x esté vinculado en el tiempo de ejecución. La primera vez que llamamos a b , escribimos en x2 como se explicó anteriormente, pero la segunda vez, escribimos en x1 , ¡ya que eso es lo que está arriba de la pila! ( x => x2 aparece cuando c vuelve).

Por lo tanto, aquí está el código de su profesor, anotado con qué variable exacta se utiliza en el que escribir con alcance léxico. Las escrituras que terminan impresas al final del programa están marcadas con un * :

program A()
{
    x, y, z: integer; // x1, y1, z1

    procedure B()
    {
        y: integer; // y2
        y=0; // y2 = 0
        x=z+1; // x1 = z1 + 1 = 12 + 1 = 13*
        z=y+2; // z1 = y2 + 2 = 0 + 2 = 2*
    }

    procedure C()
    {
        z: integer; // z2

        procedure D()
        {
            x: integer;  // x2
            x = z + 1; // x2 = z2 + 1 = 5 + 1 = 6
            y = x + 1; // y1 = x2 + 1 = 6 + 1 = 7*
            call B();
        }

        z = 5; // z2 = 5
        call D();
    }

    x = 10; // x1 = 10
    y = 11; // y1 = 11
    z = 12; // z1 = 12
    call C();
    print x, y, z; // x1, y1, z1
}

Y aquí está con alcance dinámico. Tenga en cuenta que los únicos cambios están en B y en la ubicación de las etiquetas * :

program A()
{
    x, y, z: integer; // x1, y1, z1

    procedure B()
    {
        y: integer; // y2
        y=0; // y2 = 0
        x=z+1; // x2 = z2 + 1 = 5 + 1 = 6
        z=y+2; // z2 = y2 + 2 = 0 + 2 = 2
    }

    procedure C()
    {
        z: integer; // z2

        procedure D()
        {
            x: integer;  // x2
            x = z + 1; // x2 = z2 + 1 = 5 + 1 = 6
            y = x + 1; // y1 = x2 + 1 = 6 + 1 = 7*
            call B();
        }

        z = 5; // z2 = 5
        call D();
    }

    x = 10; // x1 = 10*
    y = 11; // y1 = 11
    z = 12; // z1 = 12*
    call C();
    print x, y, z;
}

Answer 2

El alcance estático y el alcance dinámico son formas diferentes de encontrar una variable en particular con un nombre único específico en un programa escrito en cualquier idioma.

Es especialmente útil para el intérprete o compilador para decidir dónde y cómo encontrar la variable.

Considera que el código es como a continuación,

f2(){

   f1(){
   }

   f3(){
    f1()
   }

}

Estático:

Esto es básicamente textual, la primera variable definida o no se verificará en la función local (digamos nombre f1 ()), si no en la función local f1 (), entonces la variable se buscará en la función f2 () que encerró esta función (con esto quiero decir f1 ()), ... esto continúa ... hasta que se encuentre la variable.

Dinámica:

Esto es diferente de estático, en el sentido, ya que es más tiempo de ejecución o dinámico, la primera variable definida o no se verificará en la función local, si no en la función local f1 (), entonces la variable se buscará en la función f3 ( ) que llamó a esta función (con esto quiero decir f1 () de nuevo), ... esto continúa ... hasta que se encuentre la variable.

Answer 3

El quid es que el gráfico léxico se ve así:

B <- A -> C -> D

mientras que el gráfico de llamadas se ve así:

     A -> C -> D -> B

La única diferencia es qué linaje B tiene. En la imagen léxica, B se define directamente en el alcance de A (el alcance global). En la imagen dinámica, la pila en B ya tiene D en la parte superior de C y luego A.

Esta diferencia equivale a cómo las palabras clave x y z se resuelven en B. Léxicamente, se identifican con Ax y Az , pero dinámicamente, se identifican con Dx y (dado que no existe Dz ) con Cz .

def B:
    B.y = 0
    x = z + 1
    z = y + 2
def C:
    def D:
        D.x = z + 1
        y = D.x + 1
        call B
    C.z = 5
    call D
A.x, A.y, A.z = 10, 11, 12
call C
print A.x, A.y, A.z

Más arriba intenté representar tu código más claramente. Tenga en cuenta que D muta Ay acuerdo con ambos métodos de resolución de nombres, mientras que B solo muta Ax y Az si se elige el alcance léxico en lugar de dinámico.

Tenga en cuenta que, si bien una función solo se define una vez *, es común llamarla desde múltiples lugares (e incluso puede llamarse recursivamente). Por lo tanto, si bien es bastante trivial realizar un alcance léxico usando el código estático, el alcance dinámico es más complicado porque la misma palabra clave (en la misma función) puede resolverse en diferentes variables (desde diferentes espacios de nombre) durante diferentes llamadas a esa función ( requiriendo que revises el programa y rastreas cómo la pila de llamadas cambia durante la ejecución).

* (Excepto en lenguajes de plantillas ...)