cek-scheme-0.1.0.2: src/Cek/Scheme.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}
-- |
-- Module : Cek.Examples.Scheme
-- Description : Call-by-Value Scheme interpreter showcasing Generic1 Dissection and O(1) CoW call/cc.
--
-- Demonstrates how a language can combine automatic polynomial functor dissection
-- ('Dissectable' derived via 'Generic1') for uniform left-to-right expression spines
-- with explicit control and state effects ('SCallCC', 'SSet') backed by 'KontStack'
-- and 'SoAStore'.
--
-- === Architecture of the Scheme Showcase
--
-- The Scheme interpreter models R5RS/R7RS Call-by-Value semantics:
--
-- 1. Pure syntactic expressions (such as arithmetic operations 'SAdd', 'SSub', 'SMul',
-- comparisons 'SEq', and sequencing 'SSeq') require zero manual frame management:
-- they are evaluated left-to-right automatically by GHC's derived 'Generic1'
-- dissection ('FT_PureDissect').
-- 2. Mutable variables (@set!@) manipulate memory cells allocated in the unboxed 'SoAStore'.
-- 3. First-class continuations (@call/cc@) capture the entire 32-frame unrolled
-- 'KontStack' in strictly $O(1)$ time via Copy-on-Write ('captureKontSoA').
-- Invoking a captured continuation reinstates the execution context immediately
-- ('restoreKontSoA') with zero stack unwinding overhead.
--
-- > **Demonstrative Reference Implementation**: This package is an educational
-- > and demonstrative reference implementation showcasing CEK machine execution with
-- > first-class continuations (@call/cc@), mutable lexical state, and automatic
-- > GHC 'Generic1' polynomial functor dissection. It is provided primarily as an
-- > executable architectural example within the @cek@ ecosystem documentation.
--
module Cek.Scheme
( -- * Syntax Functors and Trees
Fix(..)
, SchemeF(..)
, SchemeTerm
-- * Values and Environments
, SchemeVal(..)
, SchemeEnv(..)
, SchemeError(..)
-- * Continuation Frame Tags
, pattern FT_SchemeIf
, pattern FT_SchemeSet
, pattern FT_SchemeCallCC
, pattern FT_SchemeAppFn
, pattern FT_SchemeAppArgs
-- * Evaluator Entry Point
, evalScheme
) where
import Control.Monad.ST (ST, runST)
import Data.Bits (shiftR, (.&.))
import Data.Int (Int32)
import Data.Primitive.ByteArray (writeByteArray)
import Data.Primitive.SmallArray
( SmallArray
, indexSmallArray
, readSmallArray
, sizeofSmallArray
, smallArrayFromList
, writeSmallArray
)
import GHC.Exts (unsafeCoerce#)
import GHC.Generics (Generic1)
import Cek.Core.Dissect (Dissect, Dissectable(..))
import Cek.Pykinos.Kont
( CapturedKont(..)
, FrameTag(..)
, KontStack
, captureKontSoA
, newKontStack
, pattern FT_PureDissect
, popFrameSoA
, pushFrameSoA
, restoreKontSoA
)
import Cek.Pykinos.Store
( SoAStore(..)
, StoreChunk(..)
, acquireSlot
, newSoAStore
, pattern CT_WRecord
, unCellTag
)
-- | Fixed-point wrapper for recursive syntax functors.
newtype Fix f = In { out :: f (Fix f) }
-- | Base pattern functor for the Call-by-Value Scheme showcase calculus.
--
-- Uniform expression nodes ('SAdd', 'SSub', 'SMul', 'SEq', 'SSeq') are handled
-- automatically by the derived 'Generic1' 'Dissectable' instance.
-- Special binding/control forms ('SVar', 'SLam', 'SLet', 'SSet', 'SIf', 'SCallCC', 'SApp')
-- are intercepted in the evaluator before entering generic dissection.
data SchemeF r
= SLit !Int32
-- ^ 32-bit signed integer literal constant.
| SBool !Bool
-- ^ Boolean literal constant (@#t@ or @#f@).
| SVar !Int
-- ^ Lexical variable reference indexed by De Bruijn offset into 'SchemeEnv'.
| SLam !Int !r
-- ^ Lambda abstraction with arity and body term.
| SLet !r !r
-- ^ Let binding @(let ((x rhs)) body)@ desugared to immediate 1-argument application.
| SSet !Int !r
-- ^ Mutable lexical assignment @(set! var rhs)@ mutating the 'SoAStore' cell in place.
| SIf !r !r !r
-- ^ Short-circuiting conditional expression @(if cond thenBranch elseBranch)@.
| SCallCC !r
-- ^ First-class continuation reification @(call/cc (lambda (k) ...))@.
| SApp !r ![r]
-- ^ Multi-argument function or continuation application @(fn arg0 arg1 ...)@.
| SAdd !r !r
-- ^ Pure primitive addition @(+ a b)@.
| SSub !r !r
-- ^ Pure primitive subtraction @(- a b)@.
| SMul !r !r
-- ^ Pure primitive multiplication @(* a b)@.
| SEq !r !r
-- ^ Pure primitive equality comparison @(= a b)@.
| SSeq !r !r
-- ^ Sequencing expression @(begin e1 e2)@.
deriving stock (Show, Functor, Generic1)
deriving anyclass (Dissectable)
-- | Closed syntax tree for the Scheme calculus.
type SchemeTerm = Fix SchemeF
-- | Lexical environment mapping De Bruijn indices to mutable 'SoAStore' cell addresses.
newtype SchemeEnv = SchemeEnv (SmallArray Int32)
-- | Runtime values of the Scheme abstract machine.
--
-- Note that 'VCont' holds an O(1) copy-on-write snapshot of the 32-frame SoA 'KontStack'.
data SchemeVal s
= VInt !Int32
-- ^ Evaluated integer value.
| VBool !Bool
-- ^ Evaluated boolean truth value.
| VUnit
-- ^ Evaluated unit value returned by side-effecting operations like @set!@.
| VClosure !Int !SchemeTerm !SchemeEnv
-- ^ Lexical closure capturing arity, AST body, and captured environment.
| VCont !(CapturedKont s)
-- ^ First-class captured continuation snapshot supporting multi-shot resumption.
-- | Terminal outcome or error condition for a fuel-bounded Scheme evaluation.
data SchemeError
= ErrOutOfFuel
-- ^ Evaluation step counter reached zero before termination.
| ErrTypeError !String
-- ^ Value type did not match expected operator signature.
| ErrArityMismatch !Int !Int
-- ^ Actual argument count did not match procedure arity.
| ErrUnboundVar !Int
-- ^ Variable De Bruijn index exceeded current lexical environment depth.
deriving stock (Eq, Show)
-- | Custom continuation frame tags for Scheme special forms in 'KontStack'.
pattern FT_SchemeIf :: FrameTag
pattern FT_SchemeIf = FrameTag 40
-- | Frame tag for pending assignment to a variable cell address.
pattern FT_SchemeSet :: FrameTag
pattern FT_SchemeSet = FrameTag 41
-- | Frame tag for evaluating the receiver of @call/cc@.
pattern FT_SchemeCallCC :: FrameTag
pattern FT_SchemeCallCC = FrameTag 42
-- | Frame tag for evaluating a function term before its arguments.
pattern FT_SchemeAppFn :: FrameTag
pattern FT_SchemeAppFn = FrameTag 43
-- | Frame tag for evaluating an argument list spine left-to-right.
pattern FT_SchemeAppArgs :: FrameTag
pattern FT_SchemeAppArgs = FrameTag 44
-- | Allocate a mutable value cell in 'SoAStore' and return its 'Int32' address.
{-# INLINE allocSchemeVal #-}
allocSchemeVal :: SoAStore s -> SchemeVal s -> ST s Int32
allocSchemeVal store !val = do
(!addr, StoreChunk{..}, !slot) <- acquireSlot store
writeByteArray scUnboxed slot (unCellTag CT_WRecord)
writeSmallArray scPtrA slot (unsafeCoerce# val)
pure addr
-- | Read a 'SchemeVal' from a mutable 'SoAStore' cell address in O(1) time.
{-# INLINE readSchemeVal #-}
readSchemeVal :: SoAStore s -> Int32 -> ST s (SchemeVal s)
readSchemeVal SoAStore{..} !addr = do
let !ix = fromIntegral addr :: Int
!slot = ix .&. 0xFFF
StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
unsafeCoerce# <$> readSmallArray scPtrA slot
-- | Mutate an existing 'SoAStore' cell in place (implementing Scheme @set!@).
{-# INLINE writeSchemeVal #-}
writeSchemeVal :: SoAStore s -> Int32 -> SchemeVal s -> ST s ()
writeSchemeVal SoAStore{..} !addr !val = do
let !ix = fromIntegral addr :: Int
!slot = ix .&. 0xFFF
StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
writeSmallArray scPtrA slot (unsafeCoerce# val)
-- | Extend a lexical environment with a list of freshly allocated argument addresses.
extendSchemeEnv :: [Int32] -> SchemeEnv -> SchemeEnv
extendSchemeEnv newAddrs (SchemeEnv oldArr) =
let !n = sizeofSmallArray oldArr
!oldList = [indexSmallArray oldArr i | i <- [0 .. n - 1]]
in SchemeEnv (smallArrayFromList (newAddrs ++ oldList))
-- | Safe index helper for 'SchemeEnv'.
lookupSchemeEnv :: SchemeEnv -> Int -> Maybe Int32
lookupSchemeEnv (SchemeEnv arr) !ix =
let !n = sizeofSmallArray arr
in if ix >= 0 && ix < n
then Just (indexSmallArray arr ix)
else Nothing
-- | Reduce a fully dissected pure syntax node (all children evaluated to 'SchemeVal').
reducePureScheme :: SchemeF (SchemeVal s) -> Either SchemeError (SchemeVal s)
reducePureScheme = \case
SLit n -> Right (VInt n)
SBool b -> Right (VBool b)
SAdd (VInt a) (VInt b) -> Right (VInt (a + b))
SSub (VInt a) (VInt b) -> Right (VInt (a - b))
SMul (VInt a) (VInt b) -> Right (VInt (a * b))
SEq (VInt a) (VInt b) -> Right (VBool (a == b))
SEq (VBool a) (VBool b) -> Right (VBool (a == b))
SSeq _v1 v2 -> Right v2
_ -> Left (ErrTypeError "Scheme: invalid operand types in primitive operation")
-- | Run a fuel-bounded Call-by-Value Scheme evaluation using 'KontStack' and 'SoAStore'.
--
-- Returns the terminal integer or boolean result (or 'SchemeError' on fuel exhaustion).
evalScheme :: Int -> SchemeTerm -> Either SchemeError (Either Bool Int32)
evalScheme !initialFuel rootTerm = runST $ do
store <- newSoAStore
kont <- newKontStack
let emptyEnv = SchemeEnv (smallArrayFromList [])
evalLoop store kont initialFuel rootTerm emptyEnv
where
-- Phase 1: Downward syntax traversal (Eval)
evalLoop
:: SoAStore s
-> KontStack s
-> Int
-> SchemeTerm
-> SchemeEnv
-> ST s (Either SchemeError (Either Bool Int32))
evalLoop !store !kont !fuel (In node) !env
| fuel <= 0 = pure (Left ErrOutOfFuel)
| otherwise = case node of
-- 1. Variable lookup from SoAStore
SVar ix -> case lookupSchemeEnv env ix of
Nothing -> pure (Left (ErrUnboundVar ix))
Just addr -> do
val <- readSchemeVal store addr
applyLoop store kont (fuel - 1) val
-- 2. Lambda abstraction produces a closure immediately
SLam arity body ->
applyLoop store kont (fuel - 1) (VClosure arity body env)
-- 3. Let binding: evaluate rhs, then bind in body (desugared as 1-arg app)
SLet rhs body -> do
pushFrameSoA kont FT_SchemeAppFn 0 0
(unsafeCoerce# (VClosure 1 body env))
(unsafeCoerce# ([] :: [SchemeTerm], [] :: [SchemeVal s], env))
evalLoop store kont (fuel - 1) rhs env
-- 4. Lexical mutation (set! ix rhs)
SSet ix rhs -> case lookupSchemeEnv env ix of
Nothing -> pure (Left (ErrUnboundVar ix))
Just addr -> do
pushFrameSoA kont FT_SchemeSet addr 0
(unsafeCoerce# ()) (unsafeCoerce# ())
evalLoop store kont (fuel - 1) rhs env
-- 5. Short-circuiting conditional (if cond thenBranch elseBranch)
SIf condT thenT elseT -> do
pushFrameSoA kont FT_SchemeIf 0 0
(unsafeCoerce# (thenT, elseT))
(unsafeCoerce# env)
evalLoop store kont (fuel - 1) condT env
-- 6. First-class continuation capture (call/cc receiver)
SCallCC receiverTerm -> do
pushFrameSoA kont FT_SchemeCallCC 0 0
(unsafeCoerce# env) (unsafeCoerce# ())
evalLoop store kont (fuel - 1) receiverTerm env
-- 7. Multi-argument function or continuation application
SApp fnTerm argTerms -> do
pushFrameSoA kont FT_SchemeAppArgs 0 0
(unsafeCoerce# argTerms)
(unsafeCoerce# env)
evalLoop store kont (fuel - 1) fnTerm env
-- 8. All other pure syntax nodes: delegate to Generic1 McBride Dissection!
_ -> case stepIn node of
Left valNode -> case reducePureScheme valNode of
Left err -> pure (Left err)
Right val -> applyLoop store kont (fuel - 1) val
Right (firstChild, dissected) -> do
pushFrameSoA kont FT_PureDissect 0 0
(unsafeCoerce# dissected)
(unsafeCoerce# env)
evalLoop store kont (fuel - 1) firstChild env
-- Phase 2: Upward continuation application (Apply)
applyLoop
:: SoAStore s
-> KontStack s
-> Int
-> SchemeVal s
-> ST s (Either SchemeError (Either Bool Int32))
applyLoop !store !kont !fuel !val
| fuel <= 0 = pure (Left ErrOutOfFuel)
| otherwise = do
mbFrame <- popFrameSoA kont
case mbFrame of
Nothing -> case val of
VInt n -> pure (Right (Right n))
VBool b -> pure (Right (Left b))
_ -> pure (Left (ErrTypeError "Scheme: non-primitive root result"))
Just (ft, intA, _intB, ptrA, ptrB)
-- Generic McBride Dissection frame: plug Clown 'val' and step to next Joker!
| ft == FT_PureDissect -> do
let !dis = unsafeCoerce# ptrA :: Dissect SchemeF (SchemeVal s) SchemeTerm
!env = unsafeCoerce# ptrB :: SchemeEnv
case stepNext val dis of
Left completedNode -> case reducePureScheme completedNode of
Left err -> pure (Left err)
Right val' -> applyLoop store kont (fuel - 1) val'
Right (nextTerm, dis') -> do
pushFrameSoA kont FT_PureDissect 0 0
(unsafeCoerce# dis')
(unsafeCoerce# env)
evalLoop store kont (fuel - 1) nextTerm env
-- Conditional branch selection
| ft == FT_SchemeIf -> do
let (!thenT, !elseT) = unsafeCoerce# ptrA :: (SchemeTerm, SchemeTerm)
!env = unsafeCoerce# ptrB :: SchemeEnv
case val of
VBool False -> evalLoop store kont (fuel - 1) elseT env
_ -> evalLoop store kont (fuel - 1) thenT env
-- In-place SoAStore variable mutation (set!)
| ft == FT_SchemeSet -> do
writeSchemeVal store intA val
applyLoop store kont (fuel - 1) VUnit
-- call/cc: capture O(1) CoW KontStack and invoke receiver closure
| ft == FT_SchemeCallCC -> do
captured <- captureKontSoA kont
invokeTarget store kont (fuel - 1) val [VCont captured]
-- Function evaluated; now evaluate argument spine left-to-right
| ft == FT_SchemeAppArgs -> do
let !argTerms = unsafeCoerce# ptrA :: [SchemeTerm]
!env = unsafeCoerce# ptrB :: SchemeEnv
case argTerms of
[] -> invokeTarget store kont (fuel - 1) val []
(a0 : rest) -> do
pushFrameSoA kont FT_SchemeAppFn 0 0
(unsafeCoerce# val)
(unsafeCoerce# (rest, [] :: [SchemeVal s], env))
evalLoop store kont (fuel - 1) a0 env
-- Evaluating argument list spine
| ft == FT_SchemeAppFn -> do
let !fnVal = unsafeCoerce# ptrA :: SchemeVal s
(!remArgs, !accVals, !env) =
unsafeCoerce# ptrB :: ([SchemeTerm], [SchemeVal s], SchemeEnv)
!accVals' = val : accVals
case remArgs of
[] -> invokeTarget store kont (fuel - 1) fnVal (reverse accVals')
(nextArg : moreArgs) -> do
pushFrameSoA kont FT_SchemeAppFn 0 0
(unsafeCoerce# fnVal)
(unsafeCoerce# (moreArgs, accVals', env))
evalLoop store kont (fuel - 1) nextArg env
| otherwise ->
pure (Left (ErrTypeError "Scheme: unknown continuation frame tag"))
-- Invoke either a lexical closure or a first-class captured continuation:
invokeTarget
:: SoAStore s
-> KontStack s
-> Int
-> SchemeVal s
-> [SchemeVal s]
-> ST s (Either SchemeError (Either Bool Int32))
invokeTarget !store !kont !fuel !target !args = case target of
VClosure arity body cEnv
| length args /= arity ->
pure (Left (ErrArityMismatch arity (length args)))
| otherwise -> do
argAddrs <- mapM (allocSchemeVal store) args
evalLoop store kont (fuel - 1) body (extendSchemeEnv argAddrs cEnv)
VCont captured -> case args of
[retVal] -> do
-- O(1) restoration of the captured 32-frame SoA KontStack!
restoreKontSoA kont captured
applyLoop store kont (fuel - 1) retVal
_ -> pure (Left (ErrArityMismatch 1 (length args)))
_ -> pure (Left (ErrTypeError "Scheme: attempt to call non-procedure"))