gulcii-0.3: src/Lambda.hs

{-
    gulcii -- graphical untyped lambda calculus interpreter
    Copyright (C) 2011, 2013, 2017  Claude Heiland-Allen

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-}

module Lambda (Term(..), pretty, isFreeIn, variablesIn, freeVariablesIn) where

import Data.List (nub)

import Evaluation (Strategy(..))

{-
Untyped lambda calculus terms.
-}

data Term
  = Variable String
  | Lambda Strategy String Term
  | Apply Term Term
  deriving (Read, Show, Eq, Ord)

{-
Pretty-print a term.
-}

pretty :: Term -> String
pretty = unwords . pretty'

pretty' :: Term -> [String]
pretty' (Variable v) = [v]
pretty' (Lambda k v t) = ["(", "\\", v, pretty'' k] ++ pretty' t ++ [")"]
pretty' (Apply  s t) = ["("] ++ pretty' s ++ pretty' t ++ [")"]

pretty'' :: Strategy -> String
pretty'' Strict = "!"
pretty'' Lazy = "."
pretty'' Copy = "?"

{-
Check if a variable occurs free in a term.
-}

isFreeIn :: String -> Term -> Bool
isFreeIn n (Variable v)  = n == v
isFreeIn n (Lambda _ v t)  = if n == v then False else n `isFreeIn` t
isFreeIn n (Apply t t')  = n `isFreeIn` t || n `isFreeIn` t'

{-
Get all variable names defined or referenced by a term.
-}

variablesIn :: Term -> [String]
variablesIn (Variable v)  = [v]
variablesIn (Lambda _ v t)  = nub $ v : variablesIn t
variablesIn (Apply t t')  = nub $ variablesIn t ++ variablesIn t'

{-
Get all free variables referenced by a term.
-}

freeVariablesIn :: Term -> [String]
freeVariablesIn t = filter (`isFreeIn` t) (variablesIn t)