HOFs Example in Yul

HOFsExample_yul.sol

object "ContractB" {
  code {
    datacopy(0, dataoffset("Runtime"), datasize("Runtime"))
    return(0, datasize("Runtime"))
  }
  object "Runtime" {
    code {
      let _calldata := 2048
      let _output_pointer := 0

      // This is where we keep our virtual functions
      // generated at runtime as partial function applications
      let _virtual_fns := 1024

      calldatacopy(_calldata, 0, calldatasize())

      let fn_sig := mslice(_calldata, 4)

      switch fn_sig

      // execute function
      case 0xffffffff {
        let internal_fn_sig := mslice(add(_calldata, 4), 4)
        let input_pointer := add(_calldata, 8)
        let input_size := sub(calldatasize(), 4)

        let result_length := executeNative(
          internal_fn_sig,
          input_pointer,
          input_size,
          _output_pointer,
          _virtual_fns
        )
        return (_output_pointer, result_length)
      }
      // other cases/function signatures
      default {
        mslicestore(_output_pointer, 0xeee1, 2)
        revert(_output_pointer, 2)
      }

      function executeNative(
        fsig,
        input_ptr,
        input_size,
        output_ptr,
        virtual_fns
      ) -> result_length {
        switch fsig

        // sum: a + b
        case 0xeeeeeeee {
          let a := mload(input_ptr)
          let b := mload(add(input_ptr, 32))
          mstore(output_ptr, add(a, b))
          result_length := 32
        }

        // recursiveApply, with piping outputs as input to the next function
        case 0xcccccccc {
          // number of execution steps
          let count := mslice(input_ptr, 4)

          // offsets/size in bytes for each step
          let offsets_start := add(input_ptr, 4)
          let input_inner := add(offsets_start, mul(count, 4))

          let temporary_ptr := 0x80
          let last_output_size := 0

          for { let i := 0 } lt(i, count) { i := add(i, 1) } {
            let step_length := mslice(add(offsets_start, mul(i, 4)), 4)

            // current step function signature
            let func_sig := mslice(input_inner, 4)

            // add current input after previous return value
            mmultistore(
              add(temporary_ptr, last_output_size),
              add(input_inner, 4),  // without the function signature
              sub(step_length, 4)
            )

            result_length := executeInternal(
              func_sig,
              temporary_ptr,
              add(last_output_size, sub(step_length, 4)),
              output_ptr,
              virtual_fns
            )

            // move termporary input after previous data
            temporary_ptr := add(temporary_ptr, step_length)

            // store output as new input for the next step
            mmultistore(temporary_ptr, output_ptr, result_length)
            last_output_size := result_length

            // move input pointer to the next step
            input_inner := add(input_inner, step_length)
          }
        }

        // curry: fsig, partial application argument
        case 0xbbbbbbbb {
          // first 32 bytes is the next free memory pointer
          let fpointer := mload(virtual_fns)
          if eq(fpointer, 0) {
            fpointer := add(virtual_fns, 32)
          }

          let internal_fsig := mslice(input_ptr, 4)
          let arg := mload(add(input_ptr, 4))

          // virtual function marker
          mslicestore(fpointer, 0xfefe, 2)

          // add input size (so we know how much to read)
          mstore(add(fpointer, 2), input_size)

          // store the actual data - partial application argument
          mmultistore(add(fpointer, 34), input_ptr, input_size)

          // update the free memory pointer for our curried functions references
          mstore(virtual_fns, add(fpointer, 38))

          // return the virtual function pointer
          mstore(output_ptr, fpointer)
          result_length := 32
        }

        // map: function_signature, array
        case 0xaaaaaaaa {
          let internal_fsig, fsig_size := getfSig(input_ptr)
          let array_length := mload(add(input_ptr, fsig_size))
          let values_ptr := add(add(input_ptr, fsig_size), 32)

          // build returned array - add length
          mstore(output_ptr, array_length)

          // internal_output_ptr is the memory pointer
          // at which the next array element is stored
          let internal_output_ptr := add(output_ptr, 32)
          result_length := 32

          for { let i:= 0 } lt(i, array_length) { i := add(i, 1) } {
            // Execute function on array element
            let interm_res_length := executeInternal(
              internal_fsig,
              values_ptr,
              32,
              internal_output_ptr,
              virtual_fns
            )

            // Move array values pointer & the resulting array pointer
            // to the next element
            values_ptr := add(values_ptr, 32)
            internal_output_ptr := add(internal_output_ptr, interm_res_length)

            // Update final result length
            result_length := add(result_length, interm_res_length)
          }
        }

        // reduce: function_signature, array, accumulator (initial value)
        case 0x99999999 {
          let internal_fsig, fsig_size := getfSig(input_ptr)
          let new_ptr := add(input_ptr, fsig_size)

          // The accumulator is treated as a uint256 for simplicity
          let accumulator := mload(new_ptr)
          new_ptr := add(new_ptr, 32)

          let array_length := mload(new_ptr)
          let values_ptr := add(new_ptr, 32)

          for { let i:= 0 } lt(i, array_length) { i := add(i, 1) } {
            // Store arguments in a temporary memory pointer, for simplicity
            let temporary_input_ptr := 6000
            mstore(temporary_input_ptr, accumulator)
            mstore(add(temporary_input_ptr, 32), mload(values_ptr))

            // Output memory pointer is 0x00
            let interm_res_length := executeInternal(
              internal_fsig,
              temporary_input_ptr,
              64,
              0,
              virtual_fns
            )

            // Read result from the output pointer
            accumulator := mload(0)
            // Move array values pointer to the next element
            values_ptr := add(values_ptr, 32)
          }
          mstore(output_ptr, accumulator)
          result_length := 32
        }

        // other cases/function signatures
        default {
          // revert with error code
          mslicestore(output_ptr, 0xeee2, 2)
          revert(output_ptr, 2)
        }
      }

      function executeInternal(
        fsig,
        input_ptr,
        input_size,
        output_ptr,
          virtual_fns
      ) -> result_length {
        let fsig_size := getfSigSize(fsig)

        switch fsig_size
        case 4 {
          result_length := executeNative(
            fsig,
            input_ptr,
            input_size,
            output_ptr,
            virtual_fns
          )
        }
        case 32 {
          result_length := executeCurriedFunction(
            fsig,
            input_ptr,
            input_size,
            output_ptr,
            virtual_fns
          )
        }
        default {
          // revert with error code
          mslicestore(output_ptr, 0xeee3, 2)
          revert(output_ptr, 2)
        }
      }

      function executeCurriedFunction(
        fpointer,
        input_ptr,
        input_size,
        output_ptr,
        virtual_fns
      ) -> result_length {
        // first 32 bytes are the input size
        let new_input_size := mload(add(fpointer, 2))

        // exclude input size from input ptr
        let new_input_ptr := add(fpointer, 34)

        // get curried function signature
        let fsig, fsig_size := getfSig(new_input_ptr)

        // exclude signature
        new_input_ptr := add(new_input_ptr, fsig_size)
        new_input_size := sub(new_input_size, fsig_size)

        // store the inputs for the curried function after the curried function arguments
        // effectively composing the input for the actual function that we need to run
        mmultistore(add(new_input_ptr, new_input_size), input_ptr, input_size)
        new_input_size := add(new_input_size, input_size)

        result_length := executeInternal(
          fsig,
          new_input_ptr,
          new_input_size,
          output_ptr,
          virtual_fns
        )
      }

      function getfSigSize(fsig) -> fsig_size {
        fsig_size := 4

        if lt(fsig, 10000000) {
          // check if the curried function marker exists
          // fsig is a memory pointer
          if eq(mslice(fsig, 2), 0xfefe) {
            fsig_size := 32
          }
        }
      }

      function getfSig(input_ptr) -> fsig, fsig_size {
        let fpointer := mload(input_ptr)
        fsig_size := getfSigSize(fpointer)

        switch fsig_size
        case 4 {
          fsig := mslice(input_ptr, 4)
        }
        case 32 {
          fsig := fpointer
        }
        default {
          mslicestore(0, 0xeee0, 2)
          revert(0, 2)
        }
      }

      // loads a slice of bytes in memory, where the slice <= 32 butes
      function mslice(position, length) -> result {
        result := div(
          mload(position),
          exp(2, sub(256, mul(length, 8)))
        )
      }

      // stores a slice of bytes in memory, for tight packing
      // (always shifts to left)
      function mslicestore(_ptr, val, length) {
        let slot := 32
        mstore(_ptr, shl(mul(sub(slot, length), 8), val))
      }

      // stores any number of bytes in memory
      function mmultistore(_ptr_target, _ptr_source, sizeBytes) {
        let slot := 32
        let size := div(sizeBytes, slot)

        for { let i := 0 } lt(i, size)  { i := add(i, 1) } {
          mstore(
            add(_ptr_target, mul(i, slot)),
            mload(add(_ptr_source, mul(i, slot)))
          )
        }

        let current_length :=  mul(size, slot)
        let remaining := sub(sizeBytes, current_length)
        if gt(remaining, 0) {
          mslicestore(
            add(_ptr_target, current_length),
            mslice(add(_ptr_source, current_length), remaining),
            remaining
          )
        }
      }
    }
  }
}