packages feed

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

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE EmptyCase #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

-- |
-- Module      : Cek.Core.Dissect
-- Description : McBride Clowns-and-Jokers polynomial functor dissection for CEK frames.
--
-- Automatically derives small-step continuation frames for any syntax functor
-- with a 'Generic1' instance, separating evaluated values (Clowns, left of the hole)
-- from unevaluated terms (Jokers, right of the hole).
--
-- === Theoretical Foundation: Functor Dissection
--
-- Conor McBride's classic functional pearl /"Clowns to the left of me, Jokers to the right"/
-- (POPL 2008) showed that the continuation frames of small-step abstract machines (such as
-- the CEK, SECD, and Krivine machines) are precisely the /dissections/ of syntax functors.
--
-- For any polynomial functor \(F(X)\), its dissection is a bifunctor \(F'(C, J)\) where:
--
--   * \(C\) represents /Clowns/: values in subterms to the left of the active evaluation hole
--     that have already been evaluated to weak-head or full normal forms.
--   * \(J\) represents /Jokers/: terms in subterms to the right of the active evaluation hole
--     that remain unevaluated in their initial syntactic state.
--
-- By instantiating dissection generically over GHC's 'Generic1' representation, any AST
-- functor equipped with 'DeriveGeneric1' automatically inherits correct, type-safe
-- small-step evaluation context frames without manual AST-traversal boilerplate.
--
-- === Machine Strategy Taxonomy
--
-- To support diverse evaluation semantics across the language spectrum (e.g. Scheme's
-- strict Call-by-Value, Dhall's Strong Call-by-Need, and Mercury's backtracking search),
-- the abstract machine is parameterized along three orthogonal axes:
--
--   1. 'BindPolicy': How variable bindings are captured and evaluated.
--   2. 'NormDepth': How deeply subterms are evaluated (WHNF vs full normal form).
--   3. 'ControlMode': How continuations and branching are managed.
module Cek.Core.Dissect
  ( -- * Dissection Type Classes
    Dissectable(..)
  , GDissect(..)
  , GenericDissect(..)

    -- * Dissection Representation Bifunctors
  , Void2
  , Unit2(..)
  , Sum2(..)
  , Prod2(..)
  , ListDissect(..)

    -- * Abstract Machine Classification Axes
  , BindPolicy(..)
  , NormDepth(..)
  , ControlMode(..)
  , MachineProfile(..)
  ) where

import Data.Bifunctor (Bifunctor(..))
import Data.Kind (Type)
import GHC.Generics
  ( Generic1(..)
  , K1(..)
  , M1(..)
  , Par1(..)
  , Rec1(..)
  , U1(..)
  , (:*:)(..)
  , (:+:)(..)
  )

-- | Axis 1: Variable binding evaluation strategy.
--
-- Determines when and how sub-expressions assigned to variables are evaluated:
data BindPolicy
  = BindCBV
    -- ^ Strict Call-by-Value: arguments are evaluated to values before function application
    -- (e.g. standard Scheme, ML, OCaml, and Strict Haskell).
  | BindCBN
    -- ^ Pure Call-by-Name: arguments are passed unevaluated as closures and re-evaluated
    -- on every variable reference (e.g. Algol 60, pure lambda-calculus).
  | BindNeed
    -- ^ Strong Call-by-Need / Lazy: arguments are passed as shared thunks and evaluated
    -- at most once on first reference, updating the cell in-place (e.g. Haskell, Dhall).
  deriving (Eq, Ord, Show)

-- | Axis 2: Normalization depth.
--
-- Determines whether reduction stops at top-level constructors or proceeds recursively:
data NormDepth
  = DepthWHNF
    -- ^ Weak-Head Normal Form: evaluation stops at the outermost constructor, lambda,
    -- or primitive literal. Subterms under lambdas or constructor arguments are not forced.
  | DepthNF
    -- ^ Full Normal Form: evaluation reduces terms completely under binders and constructors.
    -- Essential for type-level languages, proof assistants, and Dhall's semantic hashing.
  deriving (Eq, Ord, Show)

-- | Axis 3: Continuation and state-space branching discipline.
--
-- Governs the execution topology and multi-shot continuation capabilities:
data ControlMode
  = DetOneShot
    -- ^ Deterministic single-shot execution: the continuation stack is strictly linear
    -- and discarded upon return or unhandled exception.
  | MultiShotCtl
    -- ^ First-class multi-shot continuations: allows capturing continuations as values
    -- (e.g. Scheme's @call/cc@, delimited control operators @shift@/@reset@).
  | NondetAAM
    -- ^ Abstract Accounting Machine / Relational Search: continuation frames branch
    -- across choice-points, supporting backtracking (e.g. Prolog, Mercury, Kanren).
  deriving (Eq, Ord, Show)

-- | Compile-time profile specializing the CEK/CESK abstract machine.
--
-- Encapsulates the complete behavioral profile of an interpreter engine.
data MachineProfile = Profile
  { profBind    :: !BindPolicy
    -- ^ The binding evaluation strategy for variables and arguments.
  , profDepth   :: !NormDepth
    -- ^ The target normalization depth for expressions.
  , profControl :: !ControlMode
    -- ^ The control-flow and continuation capture capability.
  }
  deriving (Eq, Ord, Show)

-- | Class of syntax functors admitting small-step left-to-right dissection.
--
-- Any syntax functor @f@ that can be dissected yields an associated bifunctor
-- @Dissect f c j@ representing the one-hole evaluation context where:
--
--   * @c@ is the type of evaluated Clowns (values to the left of the hole).
--   * @j@ is the type of unevaluated Jokers (terms to the right of the hole).
class (Functor f, Bifunctor (Dissect f)) => Dissectable f where
  -- | Associated dissection bifunctor representing continuation frames.
  type Dissect f :: Type -> Type -> Type
  type Dissect f = GenericDissect (Rep1 f)

  -- | Enter the leftmost child hole of a syntax node.
  --
  -- Returns 'Left' with the node intact if it contains no child holes (i.e. is a leaf value),
  -- or 'Right' with the first child term @j@ paired with the continuation frame.
  stepIn :: f j -> Either (f c) (j, Dissect f c j)
  default stepIn
    :: (Generic1 f, GDissect (Rep1 f), Dissect f ~ GenericDissect (Rep1 f))
    => f j -> Either (f c) (j, Dissect f c j)
  stepIn fj = case gStepIn (from1 fj) of
    Left fc        -> Left (to1 fc)
    Right (j, dis) -> Right (j, GenericDissect dis)

  -- | Plug an evaluated value 'c' into the active hole and advance to the next hole.
  --
  -- If all child holes have been filled with evaluated values, returns 'Left' with the
  -- completed node. Otherwise, returns 'Right' with the next unevaluated child term @j@
  -- and the updated continuation frame.
  stepNext :: c -> Dissect f c j -> Either (f c) (j, Dissect f c j)
  default stepNext
    :: (Generic1 f, GDissect (Rep1 f), Dissect f ~ GenericDissect (Rep1 f))
    => c -> Dissect f c j -> Either (f c) (j, Dissect f c j)
  stepNext c (GenericDissect dis) = case gStepNext c dis of
    Left fc         -> Left (to1 fc)
    Right (j, dis') -> Right (j, GenericDissect dis')

-- | Wrapper providing a 'Bifunctor' instance for 'Generic1'-derived dissections.
newtype GenericDissect (rep :: Type -> Type) c j =
  GenericDissect (GDissectRep rep c j)

instance Bifunctor (GDissectRep rep) => Functor (GenericDissect rep c) where
  fmap g (GenericDissect d) = GenericDissect (second g d)

instance Bifunctor (GDissectRep rep) => Bifunctor (GenericDissect rep) where
  bimap f g (GenericDissect d) = GenericDissect (bimap f g d)

-- | Generic dissection algebra over GHC's 'Rep1' representation types.
--
-- Defines inductive rules for computing the derivative of sums, products, and constants.
class Bifunctor (GDissectRep rep) => GDissect (rep :: Type -> Type) where
  -- | Representation of the one-hole context for this structural representation.
  type GDissectRep rep :: Type -> Type -> Type

  -- | Step into the leftmost subterm of this representation.
  gStepIn   :: rep j -> Either (rep c) (j, GDissectRep rep c j)

  -- | Supply a value to the current hole and step to the next subterm.
  gStepNext :: c -> GDissectRep rep c j -> Either (rep c) (j, GDissectRep rep c j)

-- | Empty dissection bifunctor for nullary constructors and constant fields.
data Void2 c j deriving (Functor)

instance Bifunctor Void2 where
  bimap _ _ v = case v of {}

-- | Dissection of 'U1' (empty constructor without fields).
--
-- Since there are no fields, stepping in immediately returns 'Left U1'.
instance GDissect U1 where
  type GDissectRep U1 = Void2
  gStepIn U1    = Left U1
  gStepNext _ v = case v of {}

-- | Dissection of 'K1' (constant data field not parameterized by the recursive term).
--
-- Constant fields (such as variable names, primitive integers, strings) cannot be stepped into.
instance GDissect (K1 i a) where
  type GDissectRep (K1 i a) = Void2
  gStepIn (K1 a) = Left (K1 a)
  gStepNext _ v  = case v of {}

-- | Singleton dissection frame for a single recursive child term.
data Unit2 c j = Unit2 deriving (Eq, Show, Functor)

instance Bifunctor Unit2 where
  bimap _ _ Unit2 = Unit2

-- | Dissection of 'Par1' (the recursive parameter hole).
--
-- Stepping in immediately finds the single hole, yielding 'Unit2'.
instance GDissect Par1 where
  type GDissectRep Par1 = Unit2
  gStepIn (Par1 j)  = Right (j, Unit2)
  gStepNext c Unit2 = Left (Par1 c)

-- | Dissection through container functor 'Rec1 f'.
--
-- Delegates dissection directly to the inner 'Dissectable' container functor @f@.
instance Dissectable f => GDissect (Rec1 f) where
  type GDissectRep (Rec1 f) = Dissect f
  gStepIn (Rec1 fj) = case stepIn fj of
    Left fc       -> Left (Rec1 fc)
    Right (j, df) -> Right (j, df)
  gStepNext c df = case stepNext c df of
    Left fc        -> Left (Rec1 fc)
    Right (j, df') -> Right (j, df')

-- | Dissection through metadata wrappers 'M1'.
--
-- Passes through directly to the underlying representation.
instance GDissect f => GDissect (M1 i meta f) where
  type GDissectRep (M1 i meta f) = GDissectRep f
  gStepIn (M1 fj) = case gStepIn fj of
    Left fc       -> Left (M1 fc)
    Right (j, df) -> Right (j, df)
  gStepNext c df = case gStepNext c df of
    Left fc        -> Left (M1 fc)
    Right (j, df') -> Right (j, df')

-- | Sum dissection: disjoint union of two alternative continuation frames.
data Sum2 d1 d2 c j = InL2 !(d1 c j) | InR2 !(d2 c j)
  deriving (Eq, Show)

instance (Bifunctor d1, Bifunctor d2) => Functor (Sum2 d1 d2 c) where
  fmap g (InL2 x) = InL2 (second g x)
  fmap g (InR2 y) = InR2 (second g y)

instance (Bifunctor d1, Bifunctor d2) => Bifunctor (Sum2 d1 d2) where
  bimap f g (InL2 x) = InL2 (bimap f g x)
  bimap f g (InR2 y) = InR2 (bimap f g y)

-- | Dissection of constructor sum 'f :+: g'.
--
-- Distributes over sum alternatives: evaluates within the chosen constructor branch.
instance (GDissect f, GDissect g) => GDissect (f :+: g) where
  type GDissectRep (f :+: g) = Sum2 (GDissectRep f) (GDissectRep g)
  gStepIn (L1 fj) = case gStepIn fj of
    Left fc       -> Left (L1 fc)
    Right (j, df) -> Right (j, InL2 df)
  gStepIn (R1 gj) = case gStepIn gj of
    Left gc       -> Left (R1 gc)
    Right (j, dg) -> Right (j, InR2 dg)
  gStepNext c (InL2 df) = case gStepNext c df of
    Left fc        -> Left (L1 fc)
    Right (j, df') -> Right (j, InL2 df')
  gStepNext c (InR2 dg) = case gStepNext c dg of
    Left gc        -> Left (R1 gc)
    Right (j, dg') -> Right (j, InR2 dg')

-- | Leibniz product dissection:
--
-- By the product rule \(\partial(F \times G) = (\partial F \times G) + (F \times \partial G)\),
-- evaluation proceeds in two phases:
--
--   1. 'StepL': stepping inside the left factor @df@ while the right factor @g j@ waits as a Joker.
--   2. 'StepR': the left factor @f c@ is fully evaluated to Clowns, and stepping proceeds in @dg@.
data Prod2 f g df dg c j
  = StepL !(df c j) !(g j)
    -- ^ The left factor is currently being stepped into; right factor is unevaluated.
  | StepR !(f c)    !(dg c j)
    -- ^ The left factor is complete (all Clowns); the right factor is being stepped into.

instance (Functor g, Bifunctor df, Bifunctor dg)
      => Functor (Prod2 f g df dg c) where
  fmap g (StepL df gj) = StepL (second g df) (fmap g gj)
  fmap g (StepR fc dg) = StepR fc            (second g dg)

instance (Functor f, Functor g, Bifunctor df, Bifunctor dg)
      => Bifunctor (Prod2 f g df dg) where
  bimap f g (StepL df gj) = StepL (bimap f g df) (fmap g gj)
  bimap f g (StepR fc dg) = StepR (fmap f fc)    (bimap f g dg)

-- | Dissection of pair product 'f :*: g'.
--
-- Implements standard left-to-right applicative order evaluation across pairs of fields.
instance (Functor f, Functor g, GDissect f, GDissect g) => GDissect (f :*: g) where
  type GDissectRep (f :*: g) = Prod2 f g (GDissectRep f) (GDissectRep g)
  gStepIn (fj :*: gj) = case gStepIn fj of
    Right (j, df) -> Right (j, StepL df gj)
    Left fc       -> case gStepIn gj of
      Right (j, dg) -> Right (j, StepR fc dg)
      Left gc       -> Left (fc :*: gc)
  gStepNext c (StepL df gj) = case gStepNext c df of
    Right (j, df') -> Right (j, StepL df' gj)
    Left fc        -> case gStepIn gj of
      Right (j, dg) -> Right (j, StepR fc dg)
      Left gc       -> Left (fc :*: gc)
  gStepNext c (StepR fc dg) = case gStepNext c dg of
    Right (j, dg') -> Right (j, StepR fc dg')
    Left gc        -> Left (fc :*: gc)

-- | Dissection of a variable-arity list '[r]' into reversed Clowns and remaining Jokers.
--
-- Accumulates evaluated elements in reverse order for O(1) consing, reversing on completion.
data ListDissect c j = ListDissect ![c] ![j]
  deriving (Eq, Show)

instance Functor (ListDissect c) where
  fmap g (ListDissect cs js) = ListDissect cs (map g js)

instance Bifunctor ListDissect where
  bimap f g (ListDissect cs js) = ListDissect (map f cs) (map g js)

-- | Dissectable instance for standard lists '[]'.
--
-- Traverses elements from head to tail, evaluating each element in sequence.
instance Dissectable [] where
  type Dissect [] = ListDissect
  stepIn []       = Left []
  stepIn (j : js) = Right (j, ListDissect [] js)
  stepNext c (ListDissect cs [])       = Left (reverse (c : cs))
  stepNext c (ListDissect cs (j : js)) = Right (j, ListDissect (c : cs) js)