Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HOFs Example in Yul
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
)
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment