cek-pykinos-0.1.0.2: src/Cek/Pykinos/Kont.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}
-- |
-- Module : Cek.Pykinos.Kont
-- Description : 32-frame unrolled Structure-of-Arrays continuation stack with O(1) CoW capture.
--
-- Eliminates per-step heap closure allocation by packing 32 continuation frames
-- into a 320-byte (5 cache-line) 'MutableByteArray' paired with two pointer lanes.
--
-- === Structure-of-Arrays Continuation Design
--
-- In conventional CEK and Krivine machine implementations, every evaluation step
-- pushes a frame onto a singly-linked list of heap closures (e.g. @data Frame = ...@).
-- This incurs significant allocation overhead, GC pressure, and cache misses during
-- high-frequency interpreter loops.
--
-- 'KontStack' replaces the linked list of heap frames with an unrolled Structure-of-Arrays
-- (SoA) chain of 32-frame blocks ('KontBlock'):
--
-- * 'kbUnboxed': A 320-byte unboxed 'MutableByteArray' spanning exactly 5 cache lines:
-- * Bytes [ 0 .. 31]: Block header (Int32[0] = cursor, Int32[1] = frozenCursor).
-- * Bytes [ 32 .. 63]: Lane 0 — 32 x 1-byte 'FrameTag' opcodes.
-- * Bytes [ 64 .. 191]: Lane 1 — 32 x 4-byte 'Int32' integer fields (@intA@).
-- * Bytes [192 .. 319]: Lane 2 — 32 x 4-byte 'Int32' integer fields (@intB@).
-- * 'kbPtrA': A 32-slot 'SmallMutableArray' holding primary boxed term or record pointers.
-- * 'kbPtrB': A 32-slot 'SmallMutableArray' holding secondary boxed environment or argument pointers.
--
-- === O(1) Copy-on-Write Continuation Capture
--
-- First-class continuation capture (such as Scheme's @call/cc@ and Mercury's choice-point
-- backtracking) is achieved in strictly $O(1)$ time without copying the stack:
--
-- 1. 'captureKontSoA' records the current block and cursor in 'CapturedKont' and freezes
-- the block by updating its @frozenCursor@.
-- 2. Future pushes onto a frozen block perform a lazy copy-on-write clone of the active
-- prefix ('cloneBlockPrefix') only when modifying frozen slots.
-- 3. Unfrozen pushes and pops operate in place with zero heap allocations.
module Cek.Pykinos.Kont
( -- * Continuation Frame Opcodes
FrameTag(..)
, pattern FT_UpdateWHNF
, pattern FT_App
, pattern FT_Proj
, pattern FT_MergeL
, pattern FT_MergeR
, pattern FT_StartQuote
, pattern FT_UpdateNF
, pattern FT_QuoteBinder
, pattern FT_BuildBinder
, pattern FT_QuoteRecord
, pattern FT_QuoteSpine
, pattern FT_BuildElim
, pattern FT_PureDissect
-- * Block and Stack Structures
, KontBlock(..)
, KontStack(..)
, CapturedKont(..)
-- * Stack Lifecycle and Operations
, newKontStack
, pushFrameSoA
, popFrameSoA
, captureKontSoA
, restoreKontSoA
) where
import Control.Monad (when)
import Control.Monad.ST (ST)
import Data.Int (Int32)
import Data.Primitive.ByteArray
( MutableByteArray
, copyMutableByteArray
, newByteArray
, readByteArray
, writeByteArray
)
import Data.Primitive.SmallArray
( SmallMutableArray
, copySmallMutableArray
, newSmallArray
, readSmallArray
, writeSmallArray
)
import Data.Word (Word8)
import GHC.Exts (Any, unsafeCoerce#)
-- | Unboxed 1-byte continuation frame opcode stored in Lane 0 of 'KontBlock'.
newtype FrameTag = FrameTag { unFrameTag :: Word8 }
deriving (Eq, Ord, Show)
-- | Frame: Overwrite a lazy thunk address in the store with the evaluated WHNF value.
pattern FT_UpdateWHNF :: FrameTag
pattern FT_UpdateWHNF = FrameTag 0
-- | Frame: Apply evaluated function to pending unevaluated argument address.
pattern FT_App :: FrameTag
pattern FT_App = FrameTag 1
-- | Frame: Project a field from an evaluated record using its slot offset.
pattern FT_Proj :: FrameTag
pattern FT_Proj = FrameTag 2
-- | Frame: Merge left operand of a record union (@//@) while waiting on the right operand.
pattern FT_MergeL :: FrameTag
pattern FT_MergeL = FrameTag 3
-- | Frame: Merge right operand of a record union (@//@) with evaluated left operand.
pattern FT_MergeR :: FrameTag
pattern FT_MergeR = FrameTag 4
-- | Frame: Enter NbE quote phase to read back a value into a normal-form DAG.
pattern FT_StartQuote :: FrameTag
pattern FT_StartQuote = FrameTag 5
-- | Frame: Update a thunk's memoized normal form in Lane 1 of the store arena.
pattern FT_UpdateNF :: FrameTag
pattern FT_UpdateNF = FrameTag 6
-- | Frame: Read back a function abstraction by extending the neutral environment.
pattern FT_QuoteBinder :: FrameTag
pattern FT_QuoteBinder = FrameTag 7
-- | Frame: Reconstruct a binder term after its body has been normalized.
pattern FT_BuildBinder :: FrameTag
pattern FT_BuildBinder = FrameTag 8
-- | Frame: Normalize fields of a flat record in sequence.
pattern FT_QuoteRecord :: FrameTag
pattern FT_QuoteRecord = FrameTag 9
-- | Frame: Read back arguments in an elimination spine.
pattern FT_QuoteSpine :: FrameTag
pattern FT_QuoteSpine = FrameTag 10
-- | Frame: Reconstruct an applied neutral term from normalized arguments.
pattern FT_BuildElim :: FrameTag
pattern FT_BuildElim = FrameTag 11
-- | Frame: Generic polynomial dissection frame driving generic AST traversal.
pattern FT_PureDissect :: FrameTag
pattern FT_PureDissect = FrameTag 12
-- | A 32-frame unrolled Structure-of-Arrays block.
--
-- Layout inside the 320-byte 'kbUnboxed' 'MutableByteArray':
-- * Bytes [ 0 .. 31]: Header (Int32[0] = cursor, Int32[1] = frozenCursor)
-- * Bytes [ 32 .. 63]: Lane 0 — 32 x Word8 FrameTag opcodes
-- * Bytes [ 64 .. 191]: Lane 1 — 32 x Int32 IntA (Int32 indices 16 .. 47)
-- * Bytes [192 .. 319]: Lane 2 — 32 x Int32 IntB (Int32 indices 48 .. 79)
data KontBlock s = KontBlock
{ kbUnboxed :: !(MutableByteArray s)
-- ^ Unboxed memory holding header, frame tags, and auxiliary integer parameters.
, kbPtrA :: !(SmallMutableArray s Any)
-- ^ Primary pointer lane for closures, terms, or environments.
, kbPtrB :: !(SmallMutableArray s Any)
-- ^ Secondary pointer lane for arguments or continuation records.
, kbParent :: !(Maybe (KontBlock s))
-- ^ Previous block in the call stack when stack exceeds 32 frames.
, kbFreeChild :: !(SmallMutableArray s (Maybe (KontBlock s)))
-- ^ Cached reusable allocated child block to eliminate malloc churn during push/pop oscillation.
}
-- | Mutable reference to the active top 'KontBlock' of the continuation stack.
newtype KontStack s = KontStack (SmallMutableArray s (KontBlock s))
-- | First-class O(1) continuation snapshot for @call/cc@ and backtracking choice points.
data CapturedKont s = CapturedKont
{ ckTopBlock :: !(KontBlock s)
-- ^ Top block at the moment of capture.
, ckCursor :: {-# UNPACK #-} !Int
-- ^ Stack depth within the top block at capture time.
}
-- | Allocate an empty 32-frame SoA block linked to 'mbParent'.
{-# INLINE allocKontBlock #-}
allocKontBlock :: Maybe (KontBlock s) -> ST s (KontBlock s)
allocKontBlock !mbParent = do
mba <- newByteArray 320
writeByteArray mba 0 (0 :: Int32)
writeByteArray mba 1 (0 :: Int32)
ptrA <- newSmallArray 32 (unsafeCoerce# ())
ptrB <- newSmallArray 32 (unsafeCoerce# ())
free <- newSmallArray 1 Nothing
pure (KontBlock mba ptrA ptrB mbParent free)
-- | Create a fresh 'KontStack' with one pre-allocated 32-frame block.
newKontStack :: ST s (KontStack s)
newKontStack = do
b0 <- allocKontBlock Nothing
ref <- newSmallArray 1 b0
pure (KontStack ref)
-- | Copy-on-Write prefix clone of slots @[0 .. copyLen - 1]@ when pushing onto
-- a block that has been frozen by 'captureKontSoA'.
cloneBlockPrefix :: KontBlock s -> Int -> ST s (KontBlock s)
cloneBlockPrefix oldBlock !copyLen = do
fresh <- allocKontBlock (kbParent oldBlock)
copyMutableByteArray (kbUnboxed fresh) 0 (kbUnboxed oldBlock) 0 320
writeByteArray (kbUnboxed fresh) 0 (fromIntegral copyLen :: Int32)
writeByteArray (kbUnboxed fresh) 1 (0 :: Int32)
copySmallMutableArray (kbPtrA fresh) 0 (kbPtrA oldBlock) 0 copyLen
copySmallMutableArray (kbPtrB fresh) 0 (kbPtrB oldBlock) 0 copyLen
pure fresh
-- | Push a continuation frame onto the stack in O(1) time.
--
-- Encodes tag, two unboxed integers, and two pointer lanes with zero heap allocations.
{-# INLINE pushFrameSoA #-}
pushFrameSoA
:: KontStack s
-> FrameTag
-> Int32
-> Int32
-> Any
-> Any
-> ST s ()
pushFrameSoA (KontStack ref) !tag !intA !intB !ptrA !ptrB = do
top <- readSmallArray ref 0
cur :: Int32 <- readByteArray (kbUnboxed top) 0
frz :: Int32 <- readByteArray (kbUnboxed top) 1
if cur < 32
then do
top' <- if cur < frz
then do
c <- cloneBlockPrefix top (fromIntegral cur)
writeSmallArray ref 0 c
pure c
else pure top
let !slot = fromIntegral cur :: Int
!mba = kbUnboxed top'
writeByteArray mba (32 + slot) (unFrameTag tag)
writeByteArray mba (16 + slot) intA
writeByteArray mba (48 + slot) intB
writeSmallArray (kbPtrA top') slot ptrA
writeSmallArray (kbPtrB top') slot ptrB
writeByteArray mba 0 (cur + 1)
else do
mbChild <- readSmallArray (kbFreeChild top) 0
child <- case mbChild of
Just c -> do
writeSmallArray (kbFreeChild top) 0 Nothing
writeByteArray (kbUnboxed c) 0 (0 :: Int32)
writeByteArray (kbUnboxed c) 1 (0 :: Int32)
pure c
Nothing -> allocKontBlock (Just top)
writeSmallArray ref 0 child
let !mba = kbUnboxed child
writeByteArray mba 32 (unFrameTag tag)
writeByteArray mba 16 intA
writeByteArray mba 48 intB
writeSmallArray (kbPtrA child) 0 ptrA
writeSmallArray (kbPtrB child) 0 ptrB
writeByteArray mba 0 (1 :: Int32)
-- | Pop the topmost continuation frame from the stack in O(1) time.
--
-- Clears pointer lanes on pop to avoid memory leaks across deep recursions.
{-# INLINE popFrameSoA #-}
popFrameSoA
:: KontStack s
-> ST s (Maybe (FrameTag, Int32, Int32, Any, Any))
popFrameSoA (KontStack ref) = do
top <- readSmallArray ref 0
cur :: Int32 <- readByteArray (kbUnboxed top) 0
if cur > 0
then do
let !slot = fromIntegral (cur - 1) :: Int
readAndRetract top slot
else case kbParent top of
Nothing -> pure Nothing
Just parent -> do
writeSmallArray (kbFreeChild parent) 0 (Just top)
writeSmallArray ref 0 parent
pCur :: Int32 <- readByteArray (kbUnboxed parent) 0
if pCur > 0
then do
let !slot = fromIntegral (pCur - 1) :: Int
readAndRetract parent slot
else pure Nothing
where
readAndRetract blk !slot = do
let !mba = kbUnboxed blk
writeByteArray mba 0 (fromIntegral slot :: Int32)
!tag <- FrameTag <$> readByteArray mba (32 + slot)
!intA <- readByteArray mba (16 + slot)
!intB <- readByteArray mba (48 + slot)
!ptrA <- readSmallArray (kbPtrA blk) slot
!ptrB <- readSmallArray (kbPtrB blk) slot
frz :: Int32 <- readByteArray mba 1
when (fromIntegral slot >= frz) $ do
writeSmallArray (kbPtrA blk) slot (unsafeCoerce# ())
writeSmallArray (kbPtrB blk) slot (unsafeCoerce# ())
pure (Just (tag, intA, intB, ptrA, ptrB))
-- | Capture the current continuation in O(1) by marking the active block chain frozen.
{-# INLINE captureKontSoA #-}
captureKontSoA :: KontStack s -> ST s (CapturedKont s)
captureKontSoA (KontStack ref) = do
top <- readSmallArray ref 0
cur :: Int32 <- readByteArray (kbUnboxed top) 0
freezeChain top cur
pure (CapturedKont top (fromIntegral cur))
where
freezeChain :: KontBlock s -> Int32 -> ST s ()
freezeChain !blk !frzCursor = do
existingFrz :: Int32 <- readByteArray (kbUnboxed blk) 1
when (frzCursor > existingFrz) $
writeByteArray (kbUnboxed blk) 1 frzCursor
case kbParent blk of
Nothing -> pure ()
Just p -> freezeChain p 32
-- | Restore a previously captured continuation snapshot in O(1) time.
{-# INLINE restoreKontSoA #-}
restoreKontSoA :: KontStack s -> CapturedKont s -> ST s ()
restoreKontSoA (KontStack ref) (CapturedKont top cur) = do
writeSmallArray ref 0 top
writeByteArray (kbUnboxed top) 0 (fromIntegral cur :: Int32)