التقييم العودية المتبادلة في هاسكل

Question

تحديث: لقد اضفت إجابة الذي يصف الحل النهائي (تلميح: العازبة Expr نوع البيانات لم يكن كافيا).

---

انا جاري الكتابة مُقيِّم لغة تعبير صغيرة ، لكنني عالق في LetRec بناء.

هذه هي اللغة:

type Var = String
type Binds = [(Var, Expr)]

data Expr
  = Var     Var
  | Lam     Var    Expr
  | App     Expr   Expr
  | Con     Int
  | Sub     Expr   Expr
  | If      Expr   Expr  Expr
  | Let     Var    Expr  Expr
  | LetRec  Binds  Expr
  deriving (Show, Eq)

وهذا المقيِّم حتى الآن:

data Value
  = ValInt   Int
  | ValFun   Env   Var  Expr
  deriving (Show, Eq)

type Env = [(Var, Value)]

eval :: Env -> Expr -> Either String Value
eval env (Var x)       = maybe (throwError  $ x ++ " not found")
                               return
                               (lookup x env)
eval env (Lam x e)     = return $ ValFun env x e
eval env (App e1 e2)   = do
                         v1 <- eval env e1
                         v2 <- eval env e2
                         case v1 of
                           ValFun env1 x e -> eval ((x, v2):env1) e
                           _ -> throwError "First arg to App not a function"
eval _   (Con x)       = return $ ValInt x
eval env (Sub e1 e2)   = do
                         v1 <- eval env e1
                         v2 <- eval env e2
                         case (v1, v2) of
                           (ValInt x, ValInt y) -> return $ ValInt (x - y)
                           _ -> throwError "Both args to Sub must be ints"
eval env (If p t f)    = do 
                         v1 <- eval env p
                         case v1 of
                           ValInt x -> if x /= 0
                                       then eval env t
                                       else eval env f
                           _ -> throwError "First arg of If must be an int"
eval env (Let x e1 e2) = do
                         v1 <- eval env e1
                         eval ((x, v1):env) e2
eval env (LetRec bs e) = do
                         env' <- evalBinds
                         eval env' e
  where
    evalBinds = mfix $ \env' -> do
      env'' <- mapM (\(x, e') -> eval env' e' >>= \v -> return (x, v)) bs
      return $ nub (env'' ++ env)

هذه هي وظيفة الاختبار التي أريد تقييمها:

test3 :: Expr
test3 = LetRec [ ("even", Lam "x" (If (Var "x")
                                      (Var "odd" `App` (Var "x" `Sub` Con 1))
                                      (Con 1)
                                  ))
               , ("odd",  Lam "x" (If (Var "x")
                                      (Var "even" `App` (Var "x" `Sub` Con 1))
                                      (Con 0)
                                  ))
               ]
               (Var "even" `App` Con 5)

---

تعديل:

بناءً على إجابة ترافيس وتعليق لوك ، قمت بتحديث بلدي الشفرة لاستخدام مثيل monadfix لموناد الخطأ. المثال السابق يعمل بشكل جيد الآن! ومع ذلك ، فإن مثال الملعب لا يعمل بشكل صحيح:

test4 :: Expr
test4 = LetRec [ ("x", Con 3)
               , ("y", Var "x")
               ]
               (Con 0)

عند تقييم هذا ، حلقات المقيِّم ، ولا يحدث شيء. أظن أنني صنعت شيئًا صارمًا جدًا هنا ، لكنني لست متأكدًا مما هو عليه. هل انتهك أحد قوانين Monadfix؟

Answer 1

عندما يلقي Haskell نوبة ، عادة ما يكون هذا مؤشراً على أنك لم تفكر بوضوح في مشكلة أساسية من مشكلتك. في هذه الحالة ، والسؤال هو: الذي نموذج التقييم هل تريد استخدام لغتك؟ اتصل بالقيمة أو الاتصال بالاحترام؟

تمثيلك للبيئات مثل [(Var,Value)] يقترح أنك تريد استخدام الاتصال على حدة ، منذ كل شيء Expr يتم تقييمه إلى أ Value على الفور قبل تخزينها في البيئة. ولكن letrec لا تسير على ما يرام مع ذلك ، ويظهر مثالك الثاني!

علاوة على ذلك ، لاحظ أن نموذج التقييم للغة المضيفة (Haskell) سوف يتداخل مع نموذج التقييم للغة التي تريد تنفيذها ؛ في الواقع ، هذا ما تستخدمه حاليًا لأمثلةك: على الرغم من الغرض منها ، Valueلا يتم تقييم S إلى وضع ضعيف في الرأس الطبيعي.

ما لم يكن لديك صورة واضحة لنموذج التقييم للغة التعبير الصغيرة الخاصة بك ، فلن تحرز الكثير من التقدم letrec أو على مرافق التحقق من الخطأ.

يحرر:للحصول على مثال على مواصفات letrec في لغة كل شيء على حدة ، ألق نظرة على دليل OCAML. على أبسط مستوى ، فإنها تسمح فقط للجوانب اليمنى التي هي تعبيرات lambda ، أي الأشياء المعروفة بشكل نحلي أنها قيم.

Answer 2

ربما أفتقد شيئًا ، لكن أليس العمل التالي؟

eval env (LetRec bs ex) = eval env' ex
  where
    env' = env ++ map (\(v, e) -> (v, eval env' e)) bs

لإصدارك المحدث: ماذا عن النهج التالي؟ إنه يعمل حسب الرغبة في حالة الاختبار الخاصة بك ، ولا يرمي الأخطاء في LetRec التعبيرات:

data Value
  = ValInt Int
  | ValFun EnvWithError Var Expr
  deriving (Show, Eq)

type Env = [(Var, Value)]
type EnvWithError = [(Var, Either String Value)]

eval :: Env -> Expr -> Either String Value
eval = eval' . map (second Right)
  where
    eval' :: EnvWithError -> Expr -> Either String Value
    eval' env (Var x)        = maybe (throwError  $ x ++ " not found")
                                     (join . return)
                                     (lookup x env)
    eval' env (Lam x e)      = return $ ValFun env x e
    eval' env (App e1 e2)    = do
                               v1 <- eval' env e1
                               v2 <- eval' env e2
                               case v1 of
                                 ValFun env1 x e -> eval' ((x, Right v2):env1) e
                                 _ -> throwError "First arg to App not a function"
    eval' _   (Con x)        = return $ ValInt x
    eval' env (Sub e1 e2)    = do
                               v1 <- eval' env e1
                               v2 <- eval' env e2
                               case (v1, v2) of
                                 (ValInt x, ValInt y) -> return $ ValInt (x - y)
                                 _ -> throwError "Both args to Sub must be ints"
    eval' env (If p t f)     = do 
                               v1 <- eval' env p
                               case v1 of
                                 ValInt x -> if x /= 0
                                             then eval' env t
                                             else eval' env f
                                 _ -> throwError "First arg of If must be an int"
    eval' env (Let x e1 e2)  = do
                               v1 <- eval' env e1
                               eval' ((x, Right v1):env) e2
    eval' env (LetRec bs ex) = eval' env' ex
      where
        env' = env ++ map (\(v, e) -> (v, eval' env' e)) bs

Answer 3

الإجابة على سؤالي ؛ أردت مشاركة الحل النهائي الذي توصلت إليه.

كما هاينريش بشكل صحيح أشار, ، لم أفكر حقًا من خلال تأثير أمر التقييم.

في لغة صارمة (من خلال القيمة على أساس القيمة) ، يختلف التعبير الذي هو بالفعل قيمة (الشكل الطبيعي للرأس الضعيف) عن التعبير الذي لا يزال يحتاج إلى بعض التقييم. بمجرد تشفير هذا التمييز في نوع البيانات الخاص بي ، سقط كل شيء في مكانه:

type Var = String
type Binds = [(Var, Val)]

data Val
  = Con Int
  | Lam Var Expr
  deriving (Show, Eq)

data Expr
  = Val Val
  | Var Var
  | App Expr Expr
  | Sub Expr Expr
  | If Expr Expr Expr
  | Let Var Expr Expr
  | LetRec Binds Expr
  deriving (Show, Eq)

الفرق الوحيد مع بلدي الأصلي Expr نوع البيانات ، هو أنني سحبت مُنشئين (Con و Lam) في نوع البيانات الخاصة بهم Val. ال Expr نوع البيانات يحتوي على مُنشئ جديد Val, ، هذا يمثل حقيقة أن القيمة هي أيضًا تعبير صالح.

مع القيم في نوع البيانات الخاصة بهم ، يمكن التعامل معها بشكل منفصل عن التعبير الآخر ، على سبيل المثال letrec يمكن أن تحتوي الروابط فقط على قيم ، ولا تعبيرات أخرى.

يتم إجراء هذا التمييز أيضًا بلغات صارمة أخرى مثل C ، حيث يمكن تحديد الوظائف والثوابت فقط في النطاق العالمي.

انظر رمز كامل لوظيفة المقيّم المحدثة.