haskell - reservadas - Implementando lenguajes funcionales perezosos.

proyectos con haskell

Question

Cuando se implementa un lenguaje funcional perezoso, es necesario almacenar valores como thunks no evaluados, para ser evaluados solo cuando sea necesario.

Uno de los desafíos de una implementación eficiente, tal como se analiza en, por ejemplo, The Spineless Tagless G-machine , es que esta evaluación se debe realizar solo una vez por cada procesador, y los accesos posteriores deben reutilizar el valor calculado. al menos desaceleración cuadrática (¿quizás exponencial? No estoy seguro de lo que estoy pensando).

Estoy buscando una implementación de ejemplo simple cuya operación sea fácil de entender (a diferencia de una implementación de potencia industrial como GHC que está diseñada para un rendimiento superior a la simplicidad). Me encontré con minihaskell en http://www.andrej.com/plzoo/ que contiene el siguiente código.

Como se lo denomina "un intérprete eficiente", supongo que efectivamente realiza cada evaluación una sola vez y guarda el valor calculado para su reutilización, pero tengo dificultades para ver dónde y cómo; Solo puedo ver una declaración de asignación en el intérprete, y no parece que se esté sobrescribiendo parte de un registro de procesador.

Así que mi pregunta es si este intérprete está haciendo tal almacenamiento en caché, y si es así, ¿dónde y cómo? (Y si no, ¿cuál es la implementación existente más simple que lo hace?)

Código de http://www.andrej.com/plzoo/html/minihaskell.html

let rec interp env = function
  | Var x ->
     (try
     let r = List.assoc x env in
       match !r with
           VClosure (env'', e) -> let v = interp env'' e in r := v ; v
         | v -> v
       with
       Not_found -> runtime_error ("Unknown variable " ^ x))
   ... snipping the easy stuff ...
  | Fun _ as e -> VClosure (env, e)
  | Apply (e1, e2) ->
      (match interp env e1 with
       VClosure (env'', Fun (x, _, e)) ->
         interp ((x, ref (VClosure (env, e2)))::env'') e
     | _ -> runtime_error "Function expected in application")
  | Pair _ as e ->  VClosure (env, e)
  | Fst e ->
      (match interp env e with
       VClosure (env'', Pair (e1, e2)) -> interp env'' e1
     | _ -> runtime_error "Pair expected in fst")
  | Snd e ->
      (match interp env e with
       VClosure (env'', Pair (e1, e2)) -> interp env'' e2
     | _ -> runtime_error "Pair expected in snd")
  | Rec (x, _, e) -> 
      let rec env'' = (x,ref (VClosure (env'',e))) :: env in
    interp env'' e
  | Nil ty -> VNil ty
  | Cons _ as e -> VClosure (env, e)
  | Match (e1, _, e2, x, y, e3) ->
      (match interp env e1 with
       VNil _ -> interp env e2
     | VClosure (env'', Cons (d1, d2)) ->
         interp ((x,ref (VClosure(env'',d1)))::(y,ref (VClosure(env'',d2)))::env) e3
     | _ -> runtime_error "List expected in match")

Answer 1

Aquí hay dos intérpretes de llamada por necesidad; uno en Haskell, y uno en esquema. La clave para ambos es que puede suspender la evaluación dentro de los procedimientos sin argumentos (thunks). Ya sea que su idioma principal sea llamada por necesidad (Haskell) o llamada por valor (Esquema, ML), los formularios lambda se consideran valores, por lo que no se evaluará nada debajo de la lambda hasta que se aplique el procesador.

Entonces, cuando una función interpretada se aplica a un argumento, simplemente envuelve la representación sintáctica no evaluada del argumento en un nuevo procesador. Luego, cuando se encuentra con una variable, la busca en el entorno y evalúa rápidamente el procesador, dándole el valor del argumento.

Simplemente llegar a este punto hace que su intérprete sea perezoso, ya que los argumentos no se evalúan realmente hasta que se usan; Este es un intérprete de llamada por nombre. Sin embargo, como usted señala, un lenguaje perezoso eficiente evaluará estos argumentos solo una vez; tal lenguaje es llamada por necesidad Para obtener esta eficiencia, actualice el entorno para que en su lugar contenga un procesador que contenga solo el valor del argumento, en lugar de la expresión del argumento completo.

El primer intérprete aquí está en Haskell, y es bastante similar al código ML que pegaste. Por supuesto, los desafíos en Haskell son: 1) no implementar de manera trivial la pereza, gracias a la pereza incorporada de Haskell, y 2) aplicar los efectos secundarios en el código. Los IORef de Haskell se utilizan para permitir la actualización del entorno.

module Interp where

import Data.IORef

data Expr = ExprBool Bool
          | ExprInt Integer
          | ExprVar String
          | ExprZeroP Expr
          | ExprSub1 Expr
          | ExprMult Expr Expr
          | ExprIf Expr Expr Expr
          | ExprLam String Expr
          | ExprApp Expr Expr
          deriving (Show)

data Val = ValBool Bool                   
         | ValInt Integer
         | ValClos ((() -> IO Val) -> IO Val)

instance Show Val where
  show (ValBool b) = show b
  show (ValInt n) = show n
  show (ValClos c) = "Closure"

data Envr = EnvrEmpty                   
          | EnvrExt String (IORef (() -> IO Val)) Envr

applyEnv :: Envr -> String -> IO (IORef (() -> IO Val))
applyEnv EnvrEmpty y = error $ "unbound variable " ++ y
applyEnv (EnvrExt x v env) y =
  if x == y 
  then return v
  else applyEnv env y

eval :: Expr -> Envr -> IO Val            
eval exp env = case exp of
  (ExprBool b) -> return $ ValBool b
  (ExprInt n) -> return $ ValInt n
  (ExprVar y) -> do
    thRef <- applyEnv env y
    th <- readIORef thRef
    v <- th ()
    writeIORef thRef (/() -> return v)
    return v
  (ExprZeroP e) -> do
    (ValInt n) <- eval e env
    return $ ValBool (n == 0)
  (ExprSub1 e) -> do
    (ValInt n) <- eval e env 
    return $ ValInt (n - 1)
  (ExprMult e1 e2) -> do
    (ValInt n1) <- eval e1 env
    (ValInt n2) <- eval e2 env
    return $ ValInt (n1 * n2)
  (ExprIf te ce ae) -> do
    (ValBool t) <- eval te env
    if t then eval ce env else eval ae env
  (ExprLam x body) ->
    return $ ValClos (/a -> do
                         a'' <- newIORef a
                         eval body (EnvrExt x a'' env))
  (ExprApp rator rand) -> do
    (ValClos c) <- eval rator env 
    c (/() -> eval rand env)

-- "poor man''s Y" factorial definition      
fact = ExprApp f f
  where f = (ExprLam "f" (ExprLam "n" (ExprIf (ExprZeroP (ExprVar "n"))
                                       (ExprInt 1)
                                       (ExprMult (ExprVar "n")
                                        (ExprApp (ExprApp (ExprVar "f")
                                                  (ExprVar "f"))
                                         (ExprSub1 (ExprVar "n")))))))

-- test factorial 5 = 120            
testFact5 = eval (ExprApp fact (ExprInt 5)) EnvrEmpty            

-- Omega, the delightful infinite loop
omega = ExprApp (ExprLam "x" (ExprApp (ExprVar "x") (ExprVar "x")))
                (ExprLam "x" (ExprApp (ExprVar "x") (ExprVar "x")))

-- show that ((/y -> 5) omega) does not diverge, because the 
-- interpreter is lazy
testOmega = eval (ExprApp (ExprLam "y" (ExprInt 5)) omega) EnvrEmpty

El segundo intérprete está en Scheme, donde el único auténtico es la macro de coincidencia de patrones de Oleg. Me parece que es mucho más fácil ver de dónde viene la pereza en la versión Scheme. Las funciones del box permiten actualizar el entorno; Chez Scheme los incluye, pero he incluido definiciones que deberían funcionar para otros.

(define box
  (lambda (x)
    (cons x ''())))

(define unbox
  (lambda (b)
    (car b)))

(define set-box!
  (lambda (b v)
    (set-car! b v)))

;; Oleg Kiselyov''s linear pattern matcher
(define-syntax pmatch
  (syntax-rules (else guard)
    ((_ (rator rand ...) cs ...)
     (let ((v (rator rand ...)))
       (pmatch v cs ...)))
    ((_ v) (errorf ''pmatch "failed: ~s" v))
    ((_ v (else e0 e ...)) (begin e0 e ...))
    ((_ v (pat (guard g ...) e0 e ...) cs ...)
     (let ((fk (lambda () (pmatch v cs ...))))
       (ppat v pat (if (and g ...) (begin e0 e ...) (fk)) (fk))))
    ((_ v (pat e0 e ...) cs ...)
     (let ((fk (lambda () (pmatch v cs ...))))
       (ppat v pat (begin e0 e ...) (fk))))))

(define-syntax ppat
  (syntax-rules (uscore quote unquote)
    ((_ v uscore kt kf)
     ; _ can''t be listed in literals list in R6RS Scheme
     (and (identifier? #''uscore) (free-identifier=? #''uscore #''_))
     kt)
    ((_ v () kt kf) (if (null? v) kt kf))
    ((_ v (quote lit) kt kf) (if (equal? v (quote lit)) kt kf))
    ((_ v (unquote var) kt kf) (let ((var v)) kt))
    ((_ v (x . y) kt kf)
     (if (pair? v)
       (let ((vx (car v)) (vy (cdr v)))
     (ppat vx x (ppat vy y kt kf) kf))
       kf))
    ((_ v lit kt kf) (if (equal? v (quote lit)) kt kf))))

(define empty-env
  (lambda ()
    `(empty-env)))

(define extend-env
  (lambda (x v env)
    `(extend-env ,x ,v ,env)))

(define apply-env
  (lambda (env y)
    (pmatch env
      [(extend-env ,x ,v ,env)
       (if (eq? x y)
           v
           (apply-env env y))])))

(define value-of
  (lambda (exp env)
    (pmatch exp
      [,b (guard (boolean? b)) b]
      [,n (guard (integer? n)) n]
      [,y (guard (symbol? y))
       (let* ([box (apply-env env y)]
              [th (unbox box)]
              [v (th)])
         (begin (set-box! box (lambda () v)) v))]
      [(zero? ,e) (zero? (value-of e env))]
      [(sub1 ,e) (sub1 (value-of e env))]
      [(* ,e1 ,e2) (* (value-of e1 env) (value-of e2 env))]
      [(if ,t ,c ,a) (if (value-of t env)
                         (value-of c env)
                         (value-of a env))]
      [(lambda (,x) ,body)
       (lambda (a) (value-of body (extend-env x a env)))]
      [(,rator ,rand) ((value-of rator env)
                       (box (lambda () (value-of rand env))))])))

;; "poor man''s Y" factorial definition
(define fact
  (let ([f ''(lambda (f)
              (lambda (n)
                (if (zero? n)
                    1
                    (* n ((f f) (sub1 n))))))])
    `(,f ,f)))

;; test factorial 5 = 120
(define testFact5
  (lambda ()
    (value-of `(,fact 5) (empty-env))))

;; Omega, the delightful infinite loop
(define omega
  ''((lambda (x) (x x)) (lambda (x) (x x))))

;; show that ((lambda (y) 5) omega) does not diverge, because the interpreter
;; is lazy
(define testOmega
  (lambda ()
    (value-of `((lambda (y) 5) ,omega) (empty-env))))

Answer 2

Debería echar un vistazo a la reducción de gráficos usando combinadores (SKI). Es hermoso y simple e ilustra cómo funciona la evaluación perezosa.

Answer 3

Es posible que esté interesado en Alef ( Alef Lazily Evaluates Functions ), que es un lenguaje de programación funcional muy simple, puro y perezoso que originalmente creé específicamente para explicar la evaluación perezosa mediante la reducción de gráficos. Se implementa en menos de 500 líneas de Common Lisp, incluidas algunas funciones de visualización ordenadas. http://gergo.erdi.hu/blog/2013-02-17-write_yourself_a_haskell..._in_lisp/

Desafortunadamente, aún no he terminado de terminar ''Typecheck Yourself a Haskell ... in Lisp'', aunque la mayoría del código ya estaba escrito en la época en que publiqué la primera parte.

Answer 4

La clave son los registros: note !r , r := v . Cada vez que buscamos una variable en el entorno, en realidad recuperamos un registro, lo cual no hacemos referencia para ver si es un problema. Si es un procesador, lo evaluamos y luego guardamos el resultado. Creamos thunks durante la aplicación (observe la llamada al constructor ref ), las definiciones recursivas y la coincidencia de patrones, porque son construcciones que unen variables.