### From Stack Machine to Functional Machine: Step 2 — Currying

tags: Taylor, Ethereum, Solidity, Yul, eWasm, WebAssembly

This is a gradual introduction to my talk at the Solidity Summit, Wednesday, 29th of April at 2:50:00 PM CEST. Agenda.

### 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 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)

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 as sum (0xeeeeeeee), recursiveApply(0xcccccccc) and curry (0xbbbbbbbb). And we will call recursiveApply with a number of steps, each step is a function that has some inputs.
- executeCurriedFunction, which knows how to process curried functions
- executeInternal, 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 execute function calls recursiveApply with 000000020000002800000020bbbbbbbbeeeeeeee00000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000020
- recursiveApply breaks down the steps and runs each of them, feeding the output of each step into the next one

**Step 1**

- recursiveApply calls executeInternal with bbbbbbbbeeeeeeee0000000000000000000000000000000000000000000000000000000000000040
- executeInternal sees that the signature is 4 bytes and calls executeNative, forwarding all data
- executeNative unpacks the 0xbbbbbbbb signature and the program reaches the curry function.
- curry stores the virtual, curried function signature 0xeeeeeeee and the partially applied argument 0x0000000000000000000000000000000000000000000000000000000000000040 (64) at a memory pointer and writes that pointer into the output_ptr
- the program returns to recursiveApply, which prepares the output as input for the next step

**Step2**

- recursiveApply calls executeInternal with <sumPartial_pointer>0000000000000000000000000000000000000000000000000000000000000020
- executeInternal sees that the signature is 32 bytes and calls executeCurried, forwarding all data
- executeCurried calls executeInternal with 0xeeeeeeee0000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000000000000000000000000000000020, merging the curried function data with the new input
- executeInternal sees that the signature is 4 bytes and calls executeNative
- executeNative unpacks the 0xeeeeeeee signature and the program reaches the sum function
- sum adds the two arguments and writes the answer in the output_ptr memory pointer.
- the program returns to recursiveApply and output_ptr points at the result

**Return**

- the program returns to execute and the result from output_ptr is 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.

*Originally published at **https://github.com**.*

From Stack Machine to Functional Machine: Step 2 — Currying was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.