what is wrong with this lambda calculus program. When i try normal orde, sometimes i get…
- User
what is wrong with this lambda calculus program. When i try normal orde, sometimes i get the wrong answer:
module Lambda where
import Data.List (union, intersect) import Data.Char (chr, ord)
data Lambda = Var String | App Lambda Lambda | Abs String Lambda | Macro String
instance Show Lambda where show (Var x) = x show (App e1 e2) = "(" ++ show e1 ++ " " ++ show e2 ++ ")" show (Abs x e) = "L" ++ x ++ "." ++ show e show (Macro x) = x
-- λ
instance Eq Lambda where e1 == e2 = eq e1 e2 ([],[],[]) where eq (Var x) (Var y) (env,xb,yb) = elem (x,y) env || (not $ elem x xb || elem y yb) eq (App e1 e2) (App f1 f2) env = eq e1 f1 env && eq e2 f2 env eq (Abs x e) (Abs y f) (env,xb,yb) = eq e f ((x,y):env,x:xb,y:yb) eq (Macro x) (Macro y) _ = x == y eq _ _ _ = False
-- 1.1. vars :: Lambda -> [String] vars l = case l of Var x -> [x] App e1 e2 -> vars e1
unionvars e2 Abs x e -> [x]unionvars e Macro x -> [x]-- 1.2. freeVarsHelper :: Lambda -> [String] -> [String] freeVarsHelper l lst = case l of Var x -> if x
elemlst then [] else [x] App e1 e2 -> freeVarsHelper e1 lstunionfreeVarsHelper e2 lst Abs x e -> freeVarsHelper e (x : lst) Macro x -> if xelemlst then [] else [x]freeVars :: Lambda -> [String] freeVars l = freeVarsHelper l []
bondedVars :: Lambda -> [String] bondedVars l = filter (
notElemfreeVars l) (vars l)-- 1.3. nextString :: String -> String nextString s | null s = ['a'] | last s == 'z' = nextString (init s) ++ ['a'] | otherwise = init s ++ [nextChar (last s)] where nextChar ch = chr (ord ch + 1)
newVarHelper :: String -> [String] -> String newVarHelper s lst = if s
elemlst then newVarHelper (nextString s) lst else snewVar :: [String] -> String newVar = newVarHelper ['a']
-- 1.4. isNormalForm :: Lambda -> Bool isNormalForm l = case l of App e1 e2 -> case e1 of Abs _ _ -> False _ -> isNormalForm e1 && isNormalForm e2 Abs _ e -> isNormalForm e _ -> True
-- 1.5. changeVar :: Lambda -> String -> [String] -> Lambda changeVar l s lst = case l of Var x -> if x == s then Var newVar lst else Var x
addString :: String -> [String] -> [String] addString s lst = nextString s : lst
changeVars :: Lambda -> [String] -> [String] -> Lambda changeVars l bad lst = case bad of [] -> l x : xs -> changeVars (changeVar l x lst) xs (addString x lst)
reduceHelper :: String -> Lambda -> Lambda -> Lambda reduceHelper s l1 l2 = case l1 of Var x -> if x == s then l2 else Var x App e1 e2 -> App (reduceHelper s e1 l2) (reduceHelper s e2 l2) Abs x e -> if x == s then Abs x e else Abs x (reduceHelper s e l2) Macro x -> if x == s then l2 else Var x
reduce :: String -> Lambda -> Lambda -> Lambda reduce x e1 e2 = reduceHelper x e1 (changeVars e2 ( bondedVars e1
intersectfreeVars e2) (vars e1unionvars e2))-- 1.6. normalStep :: Lambda -> Lambda normalStep l = if isNormalForm l then l else case l of App (Abs x e1) e2 -> reduce x e1 e2 App e1 e2 -> if not (isNormalForm e1) then App (normalStep e1) e2 else App e1 (normalStep e2) -- App (normalStep e1) (normalStep e2) Abs x e -> Abs x (normalStep e) _ -> l
-- 1.7. applicativeStep :: Lambda -> Lambda applicativeStep l = if isNormalForm l then l else case l of App (Abs x1 e1) (Abs x2 e2) -> reduce x1 e1 (Abs x2 e2) App (Abs x1 e1) (Var x2) -> reduce x1 e1 (Var x2) App (Abs x1 e1) (Macro x2) -> reduce x1 e1 (Macro x2) App (Abs x e1) e2 -> App (Abs x e1) (applicativeStep e2) App e1 e2 -> App (applicativeStep e1) e2 _ -> l
-- 1.8. simplify :: (Lambda -> Lambda) -> Lambda -> [Lambda] simplify func l | isNormalForm l = [l] | otherwise = l : simplify func (func l)
normal :: Lambda -> [Lambda] normal = simplify normalStep
applicative :: Lambda -> [Lambda] applicative = simplify applicativeStep
For example on (App (App nSub n2) n1)) i get n0 istead of n1, where n0 = Abs "f" (Abs "x" vx) n1 = Abs "f" (Abs "x" (App vf vx)) n2 = Abs "f" (Abs "x" (App vf (App vf vx)))
nPred = Abs "n" (Abs "f" (Abs "x" (App (App (App vn (Abs "g" (Abs "h" (App vh (App vg vf))))) (Abs "u" vx)) (Abs "z" vz)))) nSub = Abs "n" (Abs "m" (App (App vn nPred) vm))
- Assistant
From the provided lambda calculus Haskell module and descriptions, several factors could cause unexpected behavior or "wrong answers." Here are a few issues and recommendations regarding the
normalandapplicativefunction orders, specifically applied to lambda terms likenSub,n1,n2, etc.:-
Capture of Free Variables in Substitution: Your substitution function
reduce(invoked byreduceHelper) and associated variable renaming inchangeVarsare critical because they manage variable bindings and avoid capture issues. Make sure renaming takes into account all bound and free variables in both terms being substituted to prevent accidental capture. The functions seem to attempt handling this, but proper renaming and capture-avoidance must be extensively tested. -
Reduction Order:
normalStep: Implements normal order reduction (left-most outer-most). This typically delays reduction inside abstractions (Abs) until necessary, which should be correct but can depend on adequate handling of substitutions without capturing variables.applicativeStep: Implements applicative order reduction (left-most inner-most), which is eager and reduces inside abstractions even if they aren't being applied. This can lead to different results compared to normal order if there are side effects or operations like variable binding handle differently.
-
Equality Definition: Your
Eqinstance method forLambdais critical in determining if two terms are equal when reducing and performing checks. Ensure this semantic equivalence (α-equivalence) correctly takes variable names' potential differences that otherwise represent the same binding structure into account. -
Complex Lambda Terms: The complexity of the lambda terms, such as your examples with Church numerals (
n1,n2, etc.) and operations like predecessor (nPred) and subtraction (nSub), can lead to mistakes in the encoding. Make sure these terms are correctly implemented in lambda calculus. -
Debugging and Logs: Consider adding logging at various computation stages in your reduction functions (
normalStep,reduce, etc.). This can help trace the progression of term reductions to diagnose where divergences from expected results occur. -
Thorough Testing: Implement and run a suite of test cases on all major functionalities, particularly focusing on edge cases with complex nested abstractions and applications.
Examining all these areas will likely help you pinpoint the source of the unexpected behavior. If working with complex lambda calculus expressions and their evaluations in Haskell, nuances around variable binding and scoping (due to substitution) often cause the most common pitfalls. Always ensure that renaming during substitution is correct and that all relevant variables (bound or free contextually) are considered to avoid unintended interpretations or reductions.
-