From Stack Machine to Functional Machine: Step 3 (Higher Order Functions)

Environment

  • choose Yul as the compiled language, use the raw calldata input, check the return value using the debugger.
  • use the Yul+ plugin to compile, deploy and interact (you will need to comment out the mslice helper function)

Prerequisites

Higher-Order Functions (HOFs)

Map & Curry

const sumCurried = a => b => a + b
const sumPartial = sumCurried(2)
const arr = [4, 7, 8, 2, 10]
const newarr = map(sumPartial, arr)
// newarr: [6, 9, 10, 4, 12]
// 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)
}
}
0xffffffffcccccccc0000000200000028000000c4bbbbbbbbeeeeeeee0000000000000000000000000000000000000000000000000000000000000002aaaaaaaa00000000000000000000000000000000000000000000000000000000000000050000000000000000000000000000000000000000000000000000000000000004000000000000000000000000000000000000000000000000000000000000000700000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000a
ffffffff - execute signature (main entry point)
cccccccc - recursive apply signature
00000002 - number of steps for recursive apply
00000028 - length in bytes for the first step
000000c4 - length in bytes for the second step
bbbbbbbb - first step: curry function signature
eeeeeeee - sum function signature 0000000000000000000000000000000000000000000000000000000000000002
- partially applied argument for sum: 2 aaaaaaaa - second step: map signature 0000000000000000000000000000000000000000000000000000000000000005
- array length 0000000000000000000000000000000000000000000000000000000000000004 0000000000000000000000000000000000000000000000000000000000000007 0000000000000000000000000000000000000000000000000000000000000008 0000000000000000000000000000000000000000000000000000000000000002 000000000000000000000000000000000000000000000000000000000000000a
- array values
0x000000000000000000000000000000000000000000000000000000000000000500000000000000000000000000000000000000000000000000000000000000060000000000000000000000000000000000000000000000000000000000000009000000000000000000000000000000000000000000000000000000000000000a0000000000000000000000000000000000000000000000000000000000000004000000000000000000000000000000000000000000000000000000000000000c
0000000000000000000000000000000000000000000000000000000000000005
- array length 0000000000000000000000000000000000000000000000000000000000000006 0000000000000000000000000000000000000000000000000000000000000009 000000000000000000000000000000000000000000000000000000000000000a 0000000000000000000000000000000000000000000000000000000000000004 000000000000000000000000000000000000000000000000000000000000000c
- new array values
const sumCurried = a => b => a + b
const sumPartial = sumCurried(2)
const arr = [4, 7, 8, 2, 10]
const newarr = map(sumPartial, arr)
// newarr: [6, 9, 10, 4, 12]

Reduce

const sum = (a, b) => a + bconst arr = [4, 7, 8, 2, 10]
const result = reduce(sum, arr, 0)
// result: 31
// 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
}
0xffffffffcccccccc00000001000000e899999999eeeeeeee000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000050000000000000000000000000000000000000000000000000000000000000004000000000000000000000000000000000000000000000000000000000000000700000000000000000000000000000000000000000000000000000000000000080000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000a
ffffffff - execute signature (main entry point)
cccccccc - recursive apply signature
00000001 - number of steps for recursive apply
000000e8 - length in bytes for the first step
99999999 - first step: reduce function signature
eeeeeeee - sum signature (reduce function argument) 0000000000000000000000000000000000000000000000000000000000000000
- reduce initial accumulator value 0000000000000000000000000000000000000000000000000000000000000005
- array length 0000000000000000000000000000000000000000000000000000000000000004 0000000000000000000000000000000000000000000000000000000000000007 0000000000000000000000000000000000000000000000000000000000000008 0000000000000000000000000000000000000000000000000000000000000002 000000000000000000000000000000000000000000000000000000000000000a
- array values
0x000000000000000000000000000000000000000000000000000000000000001f

Applications in Taylor

  • have runtime type checking
  • build generic functions, that can handle multiple types at runtime (Taylor only works with memory pointers)

Taylor Array Casting Example

0xfffffffe00000005777777880300000026ee000003000000070000000e000000161100000300000411000003000002220000043333331c0000001f3333331a000000030203003333332800000002040533333332000000020601
fffffffe - store graph signature
00000005 - length in bytes for the type definition head
77777788 - this graph's signature
03 - steps count
00000026 - length in bytes for hardcoded graph inputs
ee000003 - tuple of 3 elements follows
00000007 - additive sums of lengths for each tuple element
0000000e
00000016
11000003 - type uint24 for slice_size - 02
000004 - slice_size value
11000003 - type uint24 for index - 03
000002 - index value
22000004 - type bytes4 for cast signature
3333331c - cast function signature
0000001f - length in bytes for graph steps
3333331a - selectraw signature
00000003 - how many inputs selectraw will receive
02 - index for finding slice_size in all graph-local variables
03 - index for finding index
00 - index for to_type
33333328 - curry signature
00000002
04 - index for cast signature
05 - index for selectraw signature
33333332 - map signature
00000002
06 - index for curry signature
01 - index for the array to cast from
  • selectraw - we need this to select the cast_to type for an array element from the new array type. E.g. selecting 11000020 (uint256) from 22000008 44000003 11000020, where 4400000311000020 means uint256[3].
  • curry - curries the cast function & partially applies it to the selectraw result: 11000020 (cast_to type).
  • map - maps over the cast_from array elements and applies the partially applied cast function on each of them. Aggregates the results in an array.
0xffffffff77777788ee0000020000000c000000202200000844000003110000204400000312000004000000020000000500000004
ffffffff - execute function signature, the main entry point
77777788 - our array casting graph signature
ee000002 - tuple of 2 elements following
0000000c - additive sum of lengths in bytes for each tuple element
00000020
22000008 - type bytes8 for to_array
44000003 - to_array signature: uint256[3]
11000020
44000003 - actual from_array starts here, type int32[3]
12000004
00000002
00000005
00000004
0xee000001000000684400000311000020000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000050000000000000000000000000000000000000000000000000000000000000004
ee000001 - all inputs & outputs are wrapped in a tupple
00000068
44000003 - final array uint256[3]
11000020
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000005
0000000000000000000000000000000000000000000000000000000000000004
- array values: [2, 5, 7], left-padded to fit uint256

Full Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store