packages feed

cek-dhall-0.1.0.2: src/Cek/Dhall.hs

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

{- |
Module      : Cek.Dhall
Description : Felleisen-Friedman CEK abstract machine for Dhall expression normalization
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 a tailored Felleisen-Friedman CEK machine for the normalization and
evaluation of Dhall language constructs (natural numbers, integers, booleans, text,
records, projections, lists, and closures).

= Architectural Context

Per Note [Felleisen-Friedman CEK Abstract Machine] [ref:note-core-architecture],
this module models Dhall strong normalization through tail-recursive transition steps:
* Record fields are evaluated inside-out.
* Projections ('DField') resolve against fully evaluated record values.
* Operators ('DOpPlus', 'DOpTextAppend') evaluate operands strictly before combining.
-}
module Cek.Dhall
  ( -- * Dhall AST
    DhallExpr(..)
    -- * Value Domain
  , DhallVal(..)
  , DhallEnv(..)
  , emptyDhallEnv
  , extendDhallEnv
  , lookupDhallEnv
    -- * Continuation Frames
  , DhallFrame(..)
  , DhallCont
  , emptyDhallCont
    -- * Machine State & Evaluator
  , DhallState(..)
  , stepDhallCEK
  , evalDhallCEK
  ) where

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

-- | Abstract syntax for normalized Dhall expressions.
data DhallExpr
  = DVar !Text                           -- ^ Variable identifier
  | DLam !Text !DhallExpr                -- ^ Lambda abstraction (\(\lambda x. e\))
  | DApp !DhallExpr !DhallExpr           -- ^ Function application
  | DLet !Text !DhallExpr !DhallExpr     -- ^ Let-binding (@let x = e1 in e2@)
  | DNat !Word64                         -- ^ Natural literal (@+42@)
  | DInt !Integer                        -- ^ Signed integer literal (@-7@)
  | DBool !Bool                          -- ^ Boolean literal (@True@, @False@)
  | DText !Text                          -- ^ Text literal (@"hello"@)
  | DRecord ![(Text, DhallExpr)]         -- ^ Record literal (@{ x = 1, y = 2 }@)
  | DField !DhallExpr !Text              -- ^ Field selection (@r.x@)
  | DList ![DhallExpr]                   -- ^ List literal (@[1, 2, 3]@)
  | DOpPlus !DhallExpr !DhallExpr        -- ^ Natural addition (@n + m@)
  | DOpTextAppend !DhallExpr !DhallExpr  -- ^ Text concatenation (@s1 ++ s2@)
  deriving stock (Eq, Show, Generic)

-- | Normalized Dhall values.
data DhallVal
  = VNat !Word64                          -- ^ Natural number value
  | VInt !Integer                         -- ^ Integer value
  | VBool !Bool                           -- ^ Boolean value
  | VText !Text                           -- ^ Text string value
  | VClosure !Text !DhallExpr !DhallEnv   -- ^ Lexical closure \(\langle x, e, E \rangle\)
  | VRecord ![(Text, DhallVal)]           -- ^ Fully evaluated record value
  | VList ![DhallVal]                     -- ^ Evaluated list value
  deriving stock (Eq, Show, Generic)

-- | Lexical environment for Dhall evaluation.
newtype DhallEnv = DhallEnv { unDhallEnv :: [(Text, DhallVal)] }
  deriving stock (Eq, Show, Generic)

-- | Construct an empty Dhall environment.
emptyDhallEnv :: DhallEnv
emptyDhallEnv = DhallEnv []

-- | Extend a Dhall environment with a variable binding.
extendDhallEnv :: Text -> DhallVal -> DhallEnv -> DhallEnv
extendDhallEnv !x !v (DhallEnv bs) = DhallEnv ((x, v) : bs)

-- | Lookup a variable in a Dhall environment.
lookupDhallEnv :: Text -> DhallEnv -> Maybe DhallVal
lookupDhallEnv !x (DhallEnv bs) = lookup x bs

-- | Continuation frames for Dhall evaluation contexts.
data DhallFrame
  = DFrameArg !DhallExpr !DhallEnv              -- ^ Waiting for function argument
  | DFrameFun !DhallVal                         -- ^ Waiting for function body to apply
  | DFrameLet !Text !DhallExpr !DhallEnv        -- ^ Waiting for let-bound definition
  | DFrameField !Text                           -- ^ Waiting for record expression to project field
  | DFrameOpPlusR !DhallExpr !DhallEnv          -- ^ Waiting for right operand of addition
  | DFrameOpPlusL !Word64                       -- ^ Waiting to add left natural
  | DFrameOpTextR !DhallExpr !DhallEnv          -- ^ Waiting for right operand of text append
  | DFrameOpTextL !Text                         -- ^ Waiting to append left text
  deriving stock (Eq, Show, Generic)

-- | Dhall continuation stack.
type DhallCont = [DhallFrame]

-- | Construct an empty Dhall continuation stack.
emptyDhallCont :: DhallCont
emptyDhallCont = []

-- | Active state of the Dhall CEK abstract machine.
data DhallState
  = DStateEval !DhallExpr !DhallEnv !DhallCont   -- ^ Control expression \(C\), environment \(E\), continuation \(K\)
  | DStateReturn !DhallVal !DhallCont           -- ^ Value \(V\) being delivered to continuation \(K\)
  deriving stock (Eq, Show, Generic)

-- | Advance the Dhall CEK machine by a single deterministic transition step.
stepDhallCEK :: DhallState -> Either Text (Maybe DhallState)
stepDhallCEK (DStateEval expr env cont) = case expr of
  DVar x -> case lookupDhallEnv x env of
    Just val -> pure (Just (DStateReturn val cont))
    Nothing  -> Left ("Unbound variable in Dhall expression: " <> x)
  DLam x body ->
    pure (Just (DStateReturn (VClosure x body env) cont))
  DApp e1 e2 ->
    pure (Just (DStateEval e1 env (DFrameArg e2 env : cont)))
  DLet x e1 e2 ->
    pure (Just (DStateEval e1 env (DFrameLet x e2 env : cont)))
  DNat n ->
    pure (Just (DStateReturn (VNat n) cont))
  DInt i ->
    pure (Just (DStateReturn (VInt i) cont))
  DBool b ->
    pure (Just (DStateReturn (VBool b) cont))
  DText t ->
    pure (Just (DStateReturn (VText t) cont))
  DRecord fields -> do
    -- Evaluate record fields in order
    vals <- mapM (\(f, e) -> evalDhallCEKWithEnv env e >>= \v -> pure (f, v)) fields
    pure (Just (DStateReturn (VRecord vals) cont))
  DField recExpr fieldName ->
    pure (Just (DStateEval recExpr env (DFrameField fieldName : cont)))
  DList items -> do
    vals <- mapM (evalDhallCEKWithEnv env) items
    pure (Just (DStateReturn (VList vals) cont))
  DOpPlus e1 e2 ->
    pure (Just (DStateEval e1 env (DFrameOpPlusR e2 env : cont)))
  DOpTextAppend e1 e2 ->
    pure (Just (DStateEval e1 env (DFrameOpTextR e2 env : cont)))

stepDhallCEK (DStateReturn val cont) = case cont of
  [] -> pure Nothing -- Terminal state: value computed
  (DFrameArg e2 env : rest) ->
    pure (Just (DStateEval e2 env (DFrameFun val : rest)))
  (DFrameFun funVal : rest) -> case funVal of
    VClosure x body closureEnv ->
      let !newEnv = extendDhallEnv x val closureEnv
      in pure (Just (DStateEval body newEnv rest))
    _ -> Left "Type error: Attempted to apply non-function Dhall value"
  (DFrameLet x e2 env : rest) ->
    let !newEnv = extendDhallEnv x val env
    in pure (Just (DStateEval e2 newEnv rest))
  (DFrameField fieldName : rest) -> case val of
    VRecord fields -> case lookup fieldName fields of
      Just fieldVal -> pure (Just (DStateReturn fieldVal rest))
      Nothing       -> Left ("Record field not found: " <> fieldName)
    _ -> Left "Type error: Cannot project field from non-record Dhall value"
  (DFrameOpPlusR e2 env : rest) -> case val of
    VNat n1 -> pure (Just (DStateEval e2 env (DFrameOpPlusL n1 : rest)))
    _       -> Left "Type error: Left operand of + must be a Natural"
  (DFrameOpPlusL n1 : rest) -> case val of
    VNat n2 -> pure (Just (DStateReturn (VNat (n1 + n2)) rest))
    _       -> Left "Type error: Right operand of + must be a Natural"
  (DFrameOpTextR e2 env : rest) -> case val of
    VText t1 -> pure (Just (DStateEval e2 env (DFrameOpTextL t1 : rest)))
    _        -> Left "Type error: Left operand of ++ must be Text"
  (DFrameOpTextL t1 : rest) -> case val of
    VText t2 -> pure (Just (DStateReturn (VText (t1 <> t2)) rest))
    _        -> Left "Type error: Right operand of ++ must be Text"

-- | Evaluate a 'DhallExpr' under a specific lexical environment.
evalDhallCEKWithEnv :: DhallEnv -> DhallExpr -> Either Text DhallVal
evalDhallCEKWithEnv env expr = go (DStateEval expr env emptyDhallCont)
  where
    go st = case stepDhallCEK st of
      Left err -> Left err
      Right Nothing -> case st of
        DStateReturn v [] -> pure v
        _                 -> Left "Internal CEK invariant violation"
      Right (Just nextSt) -> go nextSt

-- | Evaluate a Dhall expression to its final normalized value under the empty environment.
evalDhallCEK :: DhallExpr -> Either Text DhallVal
evalDhallCEK = evalDhallCEKWithEnv emptyDhallEnv