التقييم العودية المتبادلة في هاسكل
-
29-09-2019 - |
سؤال
تحديث: لقد اضفت إجابة الذي يصف الحل النهائي (تلميح: العازبة 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؟
المحلول
عندما يلقي Haskell نوبة ، عادة ما يكون هذا مؤشراً على أنك لم تفكر بوضوح في مشكلة أساسية من مشكلتك. في هذه الحالة ، والسؤال هو: الذي نموذج التقييم هل تريد استخدام لغتك؟ اتصل بالقيمة أو الاتصال بالاحترام؟
تمثيلك للبيئات مثل [(Var,Value)]
يقترح أنك تريد استخدام الاتصال على حدة ، منذ كل شيء Expr
يتم تقييمه إلى أ Value
على الفور قبل تخزينها في البيئة. ولكن letrec
لا تسير على ما يرام مع ذلك ، ويظهر مثالك الثاني!
علاوة على ذلك ، لاحظ أن نموذج التقييم للغة المضيفة (Haskell) سوف يتداخل مع نموذج التقييم للغة التي تريد تنفيذها ؛ في الواقع ، هذا ما تستخدمه حاليًا لأمثلةك: على الرغم من الغرض منها ، Value
لا يتم تقييم S إلى وضع ضعيف في الرأس الطبيعي.
ما لم يكن لديك صورة واضحة لنموذج التقييم للغة التعبير الصغيرة الخاصة بك ، فلن تحرز الكثير من التقدم letrec
أو على مرافق التحقق من الخطأ.
يحرر:للحصول على مثال على مواصفات letrec
في لغة كل شيء على حدة ، ألق نظرة على دليل OCAML. على أبسط مستوى ، فإنها تسمح فقط للجوانب اليمنى التي هي تعبيرات lambda ، أي الأشياء المعروفة بشكل نحلي أنها قيم.
نصائح أخرى
ربما أفتقد شيئًا ، لكن أليس العمل التالي؟
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
الإجابة على سؤالي ؛ أردت مشاركة الحل النهائي الذي توصلت إليه.
كما هاينريش بشكل صحيح أشار, ، لم أفكر حقًا من خلال تأثير أمر التقييم.
في لغة صارمة (من خلال القيمة على أساس القيمة) ، يختلف التعبير الذي هو بالفعل قيمة (الشكل الطبيعي للرأس الضعيف) عن التعبير الذي لا يزال يحتاج إلى بعض التقييم. بمجرد تشفير هذا التمييز في نوع البيانات الخاص بي ، سقط كل شيء في مكانه:
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 ، حيث يمكن تحديد الوظائف والثوابت فقط في النطاق العالمي.
انظر رمز كامل لوظيفة المقيّم المحدثة.