Внедрение ленивых функциональных языков

Ответ 1

Ключом являются записи: уведомление !r, r := v. Всякий раз, когда мы просматриваем переменную из среды, мы фактически возвращаем запись, которую мы разыскиваем, чтобы увидеть, является ли это тиком. Если это удар, мы его оцениваем, а затем сохраняем результат. Мы создаем thunks во время приложения (обратите внимание на вызов конструктора ref), рекурсивные определения и сопоставление шаблонов, потому что это конструкции, которые связывают переменные.

Ответ 2

Вот два переводчика по запросу; один в Хаскелле и один в Схеме. Ключом к тому, что вы можете приостановить оценку внутри процедур без аргументов (thunks). Независимо от того, является ли ваш язык хоста по требованию (Haskell) или по умолчанию (схема, ML), лямбда-формы считаются значениями, поэтому ничто под лямбдой не будет оцениваться до тех пор, пока не будет применен thunk.

Итак, когда интерпретируемая функция применяется к аргументу, вы просто переносите необоснованное синтаксическое представление аргумента в новый thunk. Затем, когда вы сталкиваетесь с переменной, вы просматриваете ее в среде и быстро оцениваете thunk, предоставляя вам значение аргумента

Просто добраться до этой точки делает ваш переводчик ленивым, поскольку аргументы фактически не оцениваются до тех пор, пока они не будут использованы; это интерпретатор по имени. Однако, как вы отметите, эффективный ленивый язык будет оценивать эти аргументы только один раз; такой язык - это позывной. Чтобы получить эту эффективность, вы обновляете среду, чтобы вместо нее содержал thunk, содержащий только значение аргумента, а не все выражение аргумента.

Первый интерпретатор здесь находится в Haskell и довольно похож на код ML, который вы вставили. Конечно, проблемы в Haskell состоят в том, чтобы: 1) не тривиально реализовать лень, благодаря встроенной лени Haskell, и 2) прервать побочные эффекты в коде. Haskell IORef используются для обновления среды.

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 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

Второй интерпретатор находится в Схеме, где единственным реальным шаблоном является макрос совпадения с образцом Олега. Я нахожу, что гораздо легче увидеть, откуда лень приходит в версии Схемы. Функции box позволяют обновлять среду; Chez Scheme включает их, но я включил определения, которые должны работать для других.

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

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

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

;; Oleg Kiselyov 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 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))))

Ответ 3

Вы должны посмотреть на сокращение графика с помощью комбинаторов (SKI). Это красиво и просто и иллюстрирует, как работает ленивая оценка.

Ответ 4

Вам может быть интересен Alef (Alef Lazily Evaluates Functions), который представляет собой очень простой, чистый, ленивый функциональный язык программирования, который я изначально создавал специально для объяснения ленивой оценки с помощью сокращения графика. Он реализован в менее чем 500 строках Common Lisp, включая некоторые аккуратные функции визуализации. http://gergo.erdi.hu/blog/2013-02-17-write_yourself_a_haskell..._in_lisp/

К сожалению, я еще не успел закончить "Typecheck Yourself a Haskell... in Lisp", хотя большая часть кода уже была написана примерно в то время, когда я опубликовал часть 1.