From Stack Machine to Functional Machine: Step 2 - Currying
This is a gradual introduction to my talk at the Solidity Summit, Wednesday, 29th of April at 2:50:00 PM CEST. Agenda.
[ToC]
Environment
For illustrating our journey, we will use the Yul language (that compiles to Ethereum 1.0 and Wasm bytecode).
If you want to run the examples, it can be done with https://remix.ethereum.org:
- choose Yul as the compiled language, use the raw
calldatainput, check the return value using the debugger. - use the Yul+ plugin to compile, deploy and interact (you will need to comment out the
mslicehelper function)
The code example below can also be found at https://gist.github.com/loredanacirstea/1aa18e33342b862d8dc76c01b12b7dbc.
Prerequisites
Read the previous article From Stack Machine to Functional Machine: Step 1 (recursive apply).
Currying
Currying is the technique of breaking down a function that takes multiple arguments into a series of functions, each taking one or more of those arguments.
Therefore, we can write const sum = (a, b) => a + b as:
const sumCurried = a => b => a + b
const sumPartial = sumCurried(64)
sumPartial(32) // returns 96
And now we can reuse sumPartial in other places in our code, for example, as an argument to a map function: map(array, sumPartial).
In our on-chain interpreted type system Taylor, with currying, we can define classes of types. uint itself is a partially applied function and now we can reuse this function as uint(256) and we will get a concrete type.
Elastic Arity
Currying and de-currying are important tools to achieve better human-computer communication.
If the human is used to a sum function of arity 2: sum(a, b), by currying, the computer will interpret it as a composition of functions with arity 1: sum(a)(b)
If there is a family of functions of arity n, a covering function of arity n+1 can be constructed such that any one of the initial functions are called by means of an additional argument that does the selection. Having the arity dynamic may make the function much more intuitive:
sum[arity n+1] = sum[arity n](last_argument)
sum(2,3,4,5) = sum(2,3,4)(5) = ... = sum(2)(3)(4)(5)
Currying in the Ethereum Virtual Machine and WASM
Yul allows us to work directly with the stack and memory, so we have enough freedom to implement a currying system at runtime.
All that we need to do is maintain a space in memory, where our curried functions reside. In the following code, we will treat each memory pointer to a curried function as the curried function's signature.
At the memory pointer, we will find the signature of the underlying function, along with the partially-applied arguments. In our above example, this would mean <sumCurried_signature>0000000000000000000000000000000000000000000000000000000000000040 (64 = 0x40).
Now, we can use the curried function's signature in other functions and we are going to build upon the recursive apply code presented in our Step 1 article.
The following code allows us to recursively apply a series of functions, where the output of each function is fed to the next function, as input.
We have:
- some "native" functions in
executeNative, such assum(0xeeeeeeee),recursiveApply(0xcccccccc) andcurry(0xbbbbbbbb). And we will callrecursiveApplywith a number ofsteps, each step is a function that has some inputs. executeCurriedFunction, which knows how to process curried functionsexecuteInternal, which knows how to distinguish a "native" from a curried function.
Currying Example: sum(64, 32)
The calldata will be: 0xffffffffcccccccc000000020000002800000020bbbbbbbbeeeeeeee00000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000020
ffffffff - the main execute function
cccccccc - recursiveApply
00000002 - number of steps for recursiveApply
00000028 - data length in bytes for the first step
00000020 - data length in bytes for the second step
bbbbbbbb - second step starts here, with the signature for the curry function
eeeeeeee - sum function signature
0000000000000000000000000000000000000000000000000000000000000040
- partially applied argument for sum: 64
0000000000000000000000000000000000000000000000000000000000000020
- second step, with the second sum argument: 32
Program Flow
Start call
- the
executefunction callsrecursiveApplywith000000020000002800000020bbbbbbbbeeeeeeee00000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000020 recursiveApplybreaks down the steps and runs each of them, feeding the output of each step into the next one
Step 1
recursiveApplycallsexecuteInternalwithbbbbbbbbeeeeeeee0000000000000000000000000000000000000000000000000000000000000040executeInternalsees that the signature is 4 bytes and callsexecuteNative, forwarding all dataexecuteNativeunpacks the0xbbbbbbbbsignature and the program reaches thecurryfunction.currystores the virtual, curried function signature0xeeeeeeeeand the partially applied argument0x0000000000000000000000000000000000000000000000000000000000000040(64) at a memory pointer and writes that pointer into theoutput_ptr- the program returns to
recursiveApply, which prepares the output as input for the next step
Step2
recursiveApplycallsexecuteInternalwith<sumPartial_pointer>0000000000000000000000000000000000000000000000000000000000000020executeInternalsees that the signature is 32 bytes and callsexecuteCurried, forwarding all dataexecuteCurriedcallsexecuteInternalwith0xeeeeeeee0000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000000000000000000000000000000020, merging the curried function data with the new inputexecuteInternalsees that the signature is 4 bytes and callsexecuteNativeexecuteNativeunpacks the0xeeeeeeeesignature and the program reaches thesumfunctionsumadds the two arguments and writes the answer in theoutput_ptrmemory pointer.- the program returns to
recursiveApplyandoutput_ptrpoints at the result
Return
- the program returns to
executeand the result fromoutput_ptris returned
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
case 0xcccccccc {
// e.g. 2 steps:
// 000000020000002800000020
// bbbbbbbbeeeeeeee000000000000000000000000000000000000000000000000000000000000004
// 00000000000000000000000000000000000000000000000000000000000000020
// 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 existent_input_size := 0
for { let i := 0 } lt(i, count) { i := add(i, 1) } {
let step_length := mslice(add(offsets_start, mul(i, 4)), 4)
// add current input after previous return value
mmultistore(
add(temporary_ptr, existent_input_size),
input_inner,
step_length
)
result_length := executeInternal(
temporary_ptr,
add(existent_input_size, step_length),
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)
existent_input_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
}
// other cases/function signatures
default {
// revert with error code
mslicestore(output_ptr, 0xeee2, 2)
revert(output_ptr, 2)
}
}
function executeInternal(
input_ptr,
input_size,
output_ptr,
virtual_fns
) -> result_length {
let fsig, offset := getfSig(input_ptr)
switch offset
case 4 {
result_length := executeNative(
fsig,
add(input_ptr, offset),
sub(input_size, offset),
output_ptr,
virtual_fns
)
}
case 32 {
result_length := executeCurriedFunction(
fsig,
add(input_ptr, offset),
sub(input_size, offset),
output_ptr,
virtual_fns
)
}
default {
// revert with error code
mslicestore(output_ptr, 0xeee3, 2)
revert(output_ptr, 2)
}
}
function getfSig(input_ptr) -> fsig, offset {
fsig := mslice(input_ptr, 4)
offset := 4
let fpointer := mload(input_ptr)
if lt(fpointer, 10000000) {
// check if the curried function marker exists
if eq(mslice(fpointer, 2), 0xfefe) {
fsig := fpointer
offset := 32
}
}
}
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)
// 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(
new_input_ptr,
new_input_size,
output_ptr,
virtual_fns
)
}
function mslice(position, length) -> result {
result := div(
mload(position),
exp(2, sub(256, mul(length, 8)))
)
}
function mslicestore(_ptr, val, length) {
let slot := 32
mstore(_ptr, shl(mul(sub(slot, length), 8), val))
}
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
)
}
}
}
}
}
Having a technique for currying functions (at runtime) is the second step in turning a stack machine into a functional machine.
Partially applied functions can be very important when used as a map or reduce argument, allowing you to write extensible code.
Next: Step 3
In the next step, we will show you how higher-order functions can be used in this recursive engine.