Encuentro 8 - 15-9-2012 - SECD Machine

TALLER DE LENGUAJES: 08 (15/09/12)

Nico nos dió una hoja: "Landin's SECD Machine" que define una maquina abstracta.

Es una implementación de Cálculo Lambda, pensada en terminos más prácticos (performance, etc).

La máquina tiene un "estado" y las reglas de reducción definidas cambian su estado, lo cual refleja las operaciones.


  Notas sobre el contenido de la hoja:

    * E es "Enviroment"
    * Prim(op) es una operación primitiva

Evaluamos una expresión con la máquina:

  e = (\x.(\y. if x then y else false)) true false

  Llamamos, por comodidad, a las partes:

    e3 = if x then y else false
    e4 = \y.e3
    e5 = \x.e4
    e1 = e5 true
    e  = e1 false


S     E
      (nil, empty, e :: nil) :: nil <- Seteamos el Estado Inicial de la máquina

  [2] (nil, empty, e1 :: false :: App :: nil) :: nil <- Se puede aplicar la regla (2), ya que (S, E, apply(e1,e2) :: C) :: D  matchea con el estado.

  [2] (nil, empty, e5 :: true :: App :: false :: App :: nil) :: nil

  [7] ([e5;empty]::nil, empty, true :: App :: false :: App :: nil) :: nil <- Se evalua una función. Notar que se guarda el E

  [5] (true::[e5;empty]::nil, empty, true :: App :: false :: App :: nil) :: nil <- Se aplica la regla 5 (notar que la b en el papel es por "boolean", un valor booleano)

  [8] (nil,[x->true],e4::nil)::(nil,empty,false::App::nil)::nil <- Guarda, hay que entender lo del papel como "pushea en el E el mapeo variable->valor"

  [7] ([e4;[x->true]],[x->true],nil)::(nil,empty,false::App::nil)::nil

  [8] ([e4;[x->true]]::nil,empty,false::App::nil)::nil
  
  [5] (false::[e4;[x->true]]::nil,empty,App::nil)::nil

  [8] (nil,[x->true,y->false],e3::nil)::(nil,empty,nil)::nil

  [3] (nil,[x->true,y->false],x::If::y::false::nil)::(nil,empty,nil)::nil

  [6] (true::nil,[x->true,y->false],If::y::false::nil)::(nil,empty,nil)::nil

 [11] (nil,[x->true,y->false],y::nil)::(nil,empty,nil)::nil

  [6] (false::nil,[x->true,y->false],nil)::(nil,empty,nil)::nil

  [9] (false,empty,nil)::nil <- Vemos que ya no hay reglas que aplicar, y el estado es final! Wipi!

--------------------------------------------------------------------------------------------------------------------

Tarea:

  Un ejercicio como para hacer sería tratar de cambiar las reglas para que se comporte como un "Call By Name".
ċ
SECD(extended).hs
(3k)
Guillermo Polito,
Sep 17, 2012, 7:36 PM
ċ
SECD.hs
(2k)
Guillermo Polito,
Sep 16, 2012, 3:56 PM
ċ
SECD.tar.gz
(3k)
Guillermo Polito,
Sep 19, 2012, 10:03 PM
Comments