packages feed

cek-core-0.1.0.2: src/Cek/Core.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE OverloadedStrings #-}

{- |
Module      : Cek.Core
Description : Foundational Felleisen-Friedman Control-Environment-Continuation (CEK) abstract machine
Copyright   : (c) Nadia Yvette Chambers, 2026
License     : EUPL-1.2
Maintainer  : Nadia Chambers <nadia.yvette.chambers@ik.me>
Stability   : experimental
Portability : non-portable (GHC extensions)

Implements the classical Felleisen-Friedman (1986/1987) Control-Environment-Continuation (CEK)
abstract machine for call-by-value evaluation of functional expressions.

= Architectural Context

Per Note [Felleisen-Friedman CEK Abstract Machine] [ref:note-core-architecture],
this module models evaluation state transitions as an explicit 3-tuple \(\langle C, E, K \rangle\):
1. __Control (\(C\)):__ The active term undergoing reduction ('Term').
2. __Environment (\(E\)):__ Lexical scope mapping free variables to values ('Env').
3. __Continuation (\(K\)):__ Explicit evaluation context frames eliminating host stack recursion ('Cont').

= Transitions

* __Variable:__ \(\langle x, E, K \rangle \Longrightarrow \text{applyCont}(K, E(x))\)
* __Abstraction:__ \(\langle \lambda x. e, E, K \rangle \Longrightarrow \text{applyCont}(K, \text{Closure}(x, e, E))\)
* __Application:__ \(\langle e_1 \; e_2, E, K \rangle \Longrightarrow \langle e_1, E, \text{FrameArg}(e_2, E) : K \rangle\)
* __Argument Evaluated:__ \(\text{applyCont}(\text{FrameArg}(e_2, E) : K, v_1) \Longrightarrow \langle e_2, E, \text{FrameFun}(v_1) : K \rangle\)
* __Function Applied:__ \(\text{applyCont}(\text{FrameFun}(\text{Closure}(x, e, E')) : K, v_2) \Longrightarrow \langle e, E'[x \mapsto v_2], K \rangle\)
-}
module Cek.Core
  ( -- * Abstract Syntax
    Term(..)
  , Literal(..)
    -- * Value Domain & Environment
  , Value(..)
  , Env(..)
  , emptyEnv
  , extendEnv
  , lookupEnv
    -- * Continuation Frames
  , Frame(..)
  , Cont
  , emptyCont
    -- * Machine State & Execution
  , CEKState(..)
  , stepCEK
  , evalCEK
  , runCEKWithFuel
  ) where

import Data.Text (Text)
import Data.Word (Word64)
import GHC.Generics (Generic)

-- | Primitive literal values supported by the base CEK machine.
data Literal
  = LitNat !Word64        -- ^ Natural numbers
  | LitInt !Integer       -- ^ Arbitrary-precision integers
  | LitBool !Bool         -- ^ Boolean values
  | LitText !Text         -- ^ Text literals
  deriving stock (Eq, Show, Generic)

-- | Core functional term syntax.
data Term
  = Var !Text             -- ^ Variable identifier
  | Lam !Text !Term       -- ^ Anonymous lambda abstraction (\(\lambda x. e\))
  | App !Term !Term       -- ^ Function application (\(e_1 \; e_2\))
  | Lit !Literal          -- ^ Embedded literal constant
  | Let !Text !Term !Term -- ^ Let-binding (@let x = e1 in e2@)
  deriving stock (Eq, Show, Generic)

-- | Evaluated runtime values.
data Value
  = VClosure !Text !Term !Env -- ^ Lexical closure \(\langle x, e, E \rangle\)
  | VLit !Literal             -- ^ Primitive literal value
  deriving stock (Eq, Show, Generic)

-- | Lexical variable environment mapping identifiers to values.
newtype Env = Env { unEnv :: [(Text, Value)] }
  deriving stock (Eq, Show, Generic)

-- | Construct an empty lexical environment.
emptyEnv :: Env
emptyEnv = Env []

-- | Extend an environment with a new variable-to-value binding.
extendEnv :: Text -> Value -> Env -> Env
extendEnv !var !val (Env bindings) = Env ((var, val) : bindings)

-- | Look up a variable in the environment.
lookupEnv :: Text -> Env -> Maybe Value
lookupEnv !var (Env bindings) = lookup var bindings

-- | Individual continuation frame representing pending reduction context.
data Frame
  = FrameArg !Term !Env       -- ^ Waiting for function argument to evaluate
  | FrameFun !Value           -- ^ Waiting for function body to apply after argument value is ready
  | FrameLet !Text !Term !Env -- ^ Waiting for let-bound variable computation
  deriving stock (Eq, Show, Generic)

-- | Evaluation continuation stack.
type Cont = [Frame]

-- | Construct an initial empty continuation stack.
emptyCont :: Cont
emptyCont = []

-- | Active state of the CEK abstract machine.
data CEKState
  = StateEval !Term !Env !Cont  -- ^ Evaluation state: active control term \(C\), environment \(E\), continuation \(K\)
  | StateReturn !Value !Cont    -- ^ Return state: value \(V\) being passed into continuation stack \(K\)
  deriving stock (Eq, Show, Generic)

-- | Perform a single deterministic step of the CEK abstract machine.
--
-- Returns:
-- * 'Right (Just nextState)' on successful transition.
-- * 'Right Nothing' when execution terminates in a final value.
-- * 'Left err' when a runtime error (e.g. unbound variable, type mismatch) occurs.
stepCEK :: CEKState -> Either Text (Maybe CEKState)
stepCEK (StateEval term env cont) = case term of
  Var x -> case lookupEnv x env of
    Just val -> pure (Just (StateReturn val cont))
    Nothing  -> Left ("Unbound variable in CEK environment: " <> x)
  Lam x body ->
    pure (Just (StateReturn (VClosure x body env) cont))
  Lit lit ->
    pure (Just (StateReturn (VLit lit) cont))
  App e1 e2 ->
    pure (Just (StateEval e1 env (FrameArg e2 env : cont)))
  Let x e1 e2 ->
    pure (Just (StateEval e1 env (FrameLet x e2 env : cont)))

stepCEK (StateReturn val cont) = case cont of
  [] -> pure Nothing -- Terminal state: computation returned final value
  (FrameArg e2 env : restCont) ->
    pure (Just (StateEval e2 env (FrameFun val : restCont)))
  (FrameFun funVal : restCont) -> case funVal of
    VClosure x body closureEnv ->
      let !newEnv = extendEnv x val closureEnv
      in pure (Just (StateEval body newEnv restCont))
    VLit _ ->
      Left "Type error: Attempted to apply non-function literal value"
  (FrameLet x e2 env : restCont) ->
    let !newEnv = extendEnv x val env
    in pure (Just (StateEval e2 newEnv restCont))

-- | Evaluate a 'Term' to a final 'Value' under an empty environment and continuation.
evalCEK :: Term -> Either Text Value
evalCEK term = go (StateEval term emptyEnv emptyCont)
  where
    go st = case stepCEK st of
      Left err -> Left err
      Right Nothing -> case st of
        StateReturn v [] -> pure v
        _                -> Left "Internal CEK invariant violation: Terminal state without return value"
      Right (Just nextSt) -> go nextSt

-- | Fuel-bounded execution of a 'Term', returning either the computed value or fuel exhaustion.
runCEKWithFuel :: Word64 -> Term -> (Either Text Value, Word64)
runCEKWithFuel fuel term = go fuel (StateEval term emptyEnv emptyCont)
  where
    go 0 _ = (Left "OutOfFuel: Execution budget exhausted", 0)
    go !remFuel st = case stepCEK st of
      Left err -> (Left err, remFuel)
      Right Nothing -> case st of
        StateReturn v [] -> (pure v, remFuel)
        _                -> (Left "Internal CEK invariant violation", remFuel)
      Right (Just nextSt) -> go (remFuel - 1) nextSt