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

Apr 28, 2020 · 7 min read

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.

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 + bconst 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.

## Currying Example: sum(64, 32)

The `calldata` will be: `0xffffffffcccccccc000000020000002800000020bbbbbbbbeeeeeeee00000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000020`

`ffffffff - the main execute function cccccccc - recursiveApply00000002 - number of steps for recursiveApply00000028 - data length in bytes for the first step00000020 - data length in bytes for the second stepbbbbbbbb - second step starts here, with the signature for the curry functioneeeeeeee - 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`

Step 1

• `recursiveApply` calls `executeInternal` with `bbbbbbbbeeeeeeee0000000000000000000000000000000000000000000000000000000000000040`

Step2

• `recursiveApply` calls `executeInternal` with `<sumPartial_pointer>0000000000000000000000000000000000000000000000000000000000000020`

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.

## Coinmonks

Coinmonks is a non-profit Crypto educational publication.

## Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Written by

## Loredana Cirstea

Building bricks for the World Computer #ethereum #Pipeline #dType #EIP1900 https://github.com/loredanacirstea, https://www.youtube.com/c/LoredanaCirstea

## Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com