Category Archives: Funcional Programming

Applicative Order vs Normal Order

Published / by Renan Huanca / Leave a Comment

Vamos revisar la diferencia entre applicative order evaluation y normal order evaluation.

Para eso usaremos la siguiente combinación.

;; fuente: Structure and Interpretation of Computer Programs. 
;; Autores: Abelson, Sussman and Sussman
(define (p) (p) )
(define (test x y) 
	(if (= x 0)
            0
            y))

Primero veamos los conceptos:

Applicative Order Evaluation (Evaluación de orden aplicacional):
Se refiere a la estrategia de evaluación donde los argumentos de una funcion son evaluados de izquierda a derecha. También puede ser llamado post-orden.

Normal Order Evaluation (Evaluación de orden normal):
Se refiere a la estrategia de evaluación donde la expresión que esta mas afuera es primero reducida, aplicando las funciones antes de evaluar sus argumentos.

Para nuestro test vamos a evaluar:

(test 0 (p))

Con Applicative Order Evaluation

paso 0: (test 0 (p))
paso 1: (if (= 0 0)
             0
             (p))
paso 2: (if (= 0 0)
             0
             (p))
paso 3: (if (= 0 0)
             0
             (p))
paso 3: (if (= 0 0)
             0
             (p))
...

El paso 2 se va repitiendo infinitamente. Esto es por que por recursividad, el evaluador esta intentando encontrar el valor de (p), pero no lo logra, ya que la definición de (p) es (p) mismo.

Con Normal Order Evaluation

paso 0: (test 0 (p))
paso 1: (if (= 0 0)
             0
             (p))
paso 2: 0

En este caso, se evalúa la combinación hasta encontrar una llamada a una funciona primitiva. Esa función primitiva es es el if. Cuando se evalúa la función if el resultado que devuelve es 0. Y así de esta manera termina la evaluación de la combinación.

Mis conclusiones y/o comentarios

  1. Generalmente cuando nos topamos con problemas similares, usualmente seguimos el Applicative Order Evaluation. No nos damos cuenta que hay otras formas de evaluar expresiones. El Applicative Order Evaluation solo debería servirnos para describir o explicar como las expresiones son evaluadas. No debería ser la implementación.
  2. Si prueban este ejemplo en lisp van a encontrar que lisp usa el Applicative Order Evaluation, por tanto se van a encontrar con un loop infinito.
  3. Una de las grandes ventajas del Normal Order Evaluation es el laziness. Esta es una cualidad que tenemos que aplicar a nuestros programas. Especialmente en las áreas relacionadas con bigdata.
  4. Un lenguaje funcional que usa el Normal Order Evaluation es Clojure. Los reto a hacer la misma prueba en este lenguaje muy interesante.