Support accessing fields by index from BI.BuiltinList

[mesudip]

Describe the feature you'd like

When I have a BuiltinList
and I know the index of element to accessed
Then I can directly access the item by it's index

Additionally, I would like to have functions for lazy access of script context from plutus so that I don't have to remember the inices of fields.

e.g:

txInfoInputs_  bList = elemAtUnsafe 0 bList
txInfoRefInputs_ bList = elemAtUnsafe 1 bList
txInfoInputs_ bList = elemAtUnsafe 2 bList
txInfoVotes_ bList = elemAtUnsafe 12 bList

Note above function will be exported properly for each v1,v2, v3 contexts to match the field index.

Describe alternatives you've considered

• look at the TxInfo object
• find index for the field I am interested in.
• repeat that many tail and one head.

e.g

signatures :: [PubKeyHash]
signatures = unsafeFromBuiltinData  (BI.head $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail lazyTxInfo) 

[effectfully]

When I have a BuiltinList
and I know the index of element to accessed
Then I can directly access the item by it's index

Is it just (!!)?

Additionally, I would like to have functions for lazy access of script context from plutus so that I don't have to remember the inices of fields.
e.g:

txInfoInputs_  bList = elemAtUnsafe 0 bList
txInfoRefInputs_ bList = elemAtUnsafe 1 bList
txInfoInputs_ bList = elemAtUnsafe 2 bList
txInfoVotes_ bList = elemAtUnsafe 12 bList

That's a very good point. I guess maintaining backward compatibility could be annoying, @zliu41 thoughts?

[effectfully]

This doesn't seem like a high-priority issue, so I'm going to triage it as "low priority" for the time being.

[colll78]

I wrote an entire CIP about this:
cardano-foundation/CIPs#767

Please consider raising the priority of this issue. It is an extremely large pain point for production smart contract development throughout the ecosystem. Nearly every major DApp has spent a massive amount of time and effort to create black-magic heuristic solutions to achieve this.

Consider the following:

Linear search should almost never be performed in onchain code because it completely throws away what is perhaps the biggest advantage that Cardano's smart contract platform has over those in other ecosystems, namely the deterministic script evaluation property. We made huge design sacrifices to obtain this property so to not take advantage of it frankly would be like running a marathon with ankle weights. By taking advantage of this property, onchain search operations become unnecessary because we know what the list looks like at the time of transaction construction we can just pass in the index where the item we are looking for should be and fail if it is not there. We can look up anything in O(1) checks/boolean-conditions by providing the onchain code with the index (via redeemer) to where the element you want to find is supposed to be and just erroring if the indexed element is not indeed what you are looking for.

The only caveat to the above is that although search is currently O(1) in boolean-conditions (which are often the most expensive part) the cost is often still one of the biggest throughput bottlenecks for DApps because elemAt :: Integer -> [a] -> a requires a number of recursive calls (and recursion is not free in lambda calculus / Plutus Core because it is done via FixedPoint). Because of the overhead of fixed-point recursion and other CEK overhead, builtins which perform looping / recursion will always be significantly faster than manually implemented variants (see for ex integerToByteString). To reduce the impact of this overhead most production DApp codebases include some variant of elemAt with recursion-unrolling ie:

{-# INLINE elemAt' #-}
elemAt' :: Integer -> BI.BuiltinList a -> a
elemAt' !n xs =
  if n == 0 then BI.head xs else elemAt' (n - 1) (BI.tail xs)

{-# INLINE elemAtFast #-}
elemAtFast :: Integer -> BI.BuiltinList a -> a
elemAtFast !n xs
  | n > 10 = elemAtFast (n - 10) (BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail xs)
  | otherwise = elemAtFast2 n xs

{-# INLINE elemAtFast2 #-}
elemAtFast2 :: Integer -> BI.BuiltinList a -> a
elemAtFast2 !n xs
  | n > 5 = elemAtFast2 (n - 5) (BI.tail $ BI.tail $ BI.tail $ BI.tail $ BI.tail xs)
  | otherwise = elemAt' n xs```

For a set of random generated lists of integers 0-26, the above implementation is ~3-5x more efficient (65%-80% reduction in both MEM and CPU) in the average case than the naive suggested !! implementation. However, the worst-case complexity is still awful.

The suggested builtin would be a vast improvement on even the heuristic optimization, for example tail26:

tail26 :: PIsListLike l a => Term s (l a :--> a)
tail26 = plam (\xs -> ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail #$ ptail # xs)

Has 95% reduced ex-units memory compared to the naive elemAt 26 xs and 75% reduced compared to the heuristically optimized variant elemAtFast 26 xs.

[colll78]

Additionally, I would like to have functions for lazy access of script context from plutus so that I don't have to remember the inices of fields.

I have written a TH macro to do exactly this, it might be of use to you / the Plutus team:

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE DataKinds           #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TemplateHaskell     #-}
{-# LANGUAGE TypeApplications    #-}
{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
{-# HLINT ignore "Use iterate" #-}

module Cardano.Djed.Core.Types.THUtils (generateGetField, getField', GetField(..)) where

import Control.Monad
import Data.List (elemIndex)
import Data.Maybe (fromJust)
import Data.Proxy ()
import GHC.TypeLits
import Language.Haskell.TH
import PlutusTx.Builtins.Internal qualified as BI
import PlutusTx.Prelude (BuiltinData)
import Prelude

-- The contents of this module are used to generate instances of the GetField
-- typeclass for any arbitrary record type. The GetField typeclass is used to
-- extract fields from a BuiltinData value, which is a PlutusTx representation
-- of a Haskell ADT. The GetField typeclass is defined as follows:
--
-- class KnownSymbol s => GetField s where
--     getField :: BuiltinData -> BuiltinData

-- For $(generateGetField ''SCBankState), the following instances are generated:
-- instance GetField "scReserve" where
--     getField args = BI.head (BI.snd (BI.unsafeDataAsConstr args))

-- instance GetField "scN_SC" where
--     getField args = BI.head (BI.tail (BI.snd (BI.unsafeDataAsConstr args)))

-- instance GetField "scN_RC" where
--     getField args = BI.head (BI.tail (BI.tail (BI.snd (BI.unsafeDataAsConstr args))))

-- instance GetField "scLastOrder" where
--     getField args = BI.head $ BI.tail $ BI.tail $ BI.tail (BI.snd (BI.unsafeDataAsConstr args))

-- ... repeat for each field ...

-- getField' :: forall s. GetField s => BuiltinData -> BuiltinData
-- getField' = getField @s

class KnownSymbol s => GetField s where
    getField :: BuiltinData -> BuiltinData

getField' :: forall s. GetField s => BuiltinData -> BuiltinData
getField' = getField @s

-- Helper function to extract field names from a data type
getFieldNames :: Name -> Q [String]
getFieldNames name = do
  TyConI (DataD _ _ _ _ [RecC _ fields] _) <- reify name
  return [nameBase fieldName | (fieldName, _, _) <- fields]

generateGetField :: Name -> Q [Dec]
generateGetField typeName = do
  fieldNames <- getFieldNames typeName
  decs <- forM fieldNames $ \fieldName -> do
    let fieldIndex = fromJust . (`elemIndex` fieldNames)
    let getFieldFunc = FunD (mkName "getField") [Clause [VarP (mkName "args")] (NormalB (applyTails (fieldIndex fieldName) (VarE (mkName "args")))) []]
    return [InstanceD Nothing [] (AppT (ConT ''GetField) (LitT (StrTyLit fieldName))) [getFieldFunc]]
  return (concat decs)
  where
    applyTails n args = AppE (VarE 'BI.head) (foldl (\acc _ -> AppE (VarE 'BI.tail) acc) (AppE (VarE 'BI.snd) (AppE (VarE 'BI.unsafeDataAsConstr) args)) [1..n])

You can use it as follows for any data type with a single constructor.

data ScriptContext = ScriptContext
  { scriptContextTxInfo     :: TxInfo
  -- ^ information about the transaction the currently-executing script is included in
  , scriptContextRedeemer   :: V2.Redeemer
  -- ^ Redeemer for the currently-executing script
  , scriptContextScriptInfo :: ScriptInfo
  -- ^ the purpose of the currently-executing script, along with information associated
  -- with the purpose
  }
  deriving stock (Generic, Haskell.Show)
PlutusTx.makeIsDataIndexed ''ScriptContext [('ScriptContext , 0)]  
$(generateGetField ''ScriptContext)
...
$(generateGetField ''TxInfo)

myValidator :: ScriptContext -> BuiltinUnit 
myValidator ctx = if (mint == mempty) then BI.unitval else error 
  where 
  txInfo = getField @"scriptContextTxInfo" ctx 
  mint = getField @"txInfoMint" txInfo            

This is essentially a port of pfield from Plutarch which you can see here

As future work I would like to implement (or have implemented) pletFields found here for efficient access of multiple fields from a data type (because it reuses the tail of the list).