Functional Programming in Solidity

EthWarsaw 2023, 2nd Version

Miao, ZhiCheng (@hellwolf) / Superfluid

The Goals of The Talk

  • Demonstrate the possibility of limited functional programming in Solidity.
  • Show case an example of using this paradigm to build super token.
  • Make you interested in functional programming.

An Quick Example

function _doFlow(bytes memory eff,
                 address from, address to, bytes32 flowHash, FlowRate flowRate,
                 Time t)
    internal returns (bytes memory)
{
    if (from == to) return eff; // short circuit
    FlowRate flowRateDelta = flowRate - _getFlowRate(eff, flowHash);
    BasicParticle memory a = _getUIndex(eff, from);
    BasicParticle memory b = _getUIndex(eff, to);

    (a, b) = a.shift_flow2b(b, flowRateDelta, t);

    eff = _setUIndex(eff, from, a);
    eff = _setUIndex(eff, to, b);
    eff = _setFlowInfo(eff, flowHash, from, to, flowRate, flowRateDelta);

    return eff;
}

What Is Functional Programming

More "What", Less "How"

  • Implement as much code as possible in data definition, equations and logical formulas (properties).
  • For these code, strictly pure functions are your friends because of referential transparency (same input, same output!

Defer Side Effects

  • Common side effects:
    • Storage accesses.
    • Interactions with external code, aka. glue code.
    • Computation strategies.
  • To make code actually useful, implement computational strategies:
    • Built-in in most languages and taken for granted.
    • Typically as sequential programs (aka. Monads!).
    • Can be concurrent and graph computing:
      • good for distributed computing (UTXO?!),
      • think of spreadsheet as graph computing.

Why Functional Programming

"Hughes, J., 1989. Why functional programming matters."

  • The gateway drug.
  • "As software becomes more and more complex, it is more and more important to structure it well. Well-structured software is easy to write, easy to debug, and provides a collection of modules that can be re-used to reduce future programming costs"
  • Keywords: better debugging, better re-usability, less maintenance cost.

Best Way to Structure Smart Contracts

  • As an addition to extensive testing, and perhaps limited post-production formal verification.
  • "More Correctness" by construction.

What About Solidity

Solidity is no where near being able to express all functional programming ideas, but we can emulate some ideas.

Here are some techniques:

Custom Types

  • Using custom types to wrap numerical values,
  • and operator overloading (since 0.8.19).

An Example

type FlowRate is int128;

function mt_r_add_r(FlowRate a, FlowRate b) pure returns (FlowRate) {
    return FlowRate.wrap(FlowRate.unwrap(a) + FlowRate.unwrap(b));
}

function mt_r_sub_r(FlowRate a, FlowRate b) pure returns (FlowRate) {
    return FlowRate.wrap(FlowRate.unwrap(a) - FlowRate.unwrap(b));
}

using { mt_r_add_r as +, mt_r_sub_r as - } for FlowRate global;

Using Additional Library for Mixed-Types Operators

library AdditionalMonetaryTypeHelpers {
    //...
    function inv(FlowRate r) internal pure returns (FlowRate) {
        return FlowRate.wrap(-FlowRate.unwrap(r));
    }
    function mul(FlowRate r, Time t) internal pure returns (Value) {
        return Value.wrap(FlowRate.unwrap(r) * int(uint(Time.unwrap(t))));
    }
    //...
}
using AdditionalMonetaryTypeHelpers for Time global;
using AdditionalMonetaryTypeHelpers for Value global;
using AdditionalMonetaryTypeHelpers for Unit global;
using AdditionalMonetaryTypeHelpers for FlowRate global;

"Strictly" Pure Functions

"Strictly Pure":

  • NB! References types passed with the "memory" keyword can be modified by pure functions!
  • We use clone semantics rigorously to support even purer solidity functions.
/// Pure data clone function.
function clone(BasicParticle memory a) internal pure
    returns (BasicParticle memory b)
{
    b._settled_at = a._settled_at;
    b._settled_value = a._settled_value;
    b._flow_rate = a._flow_rate;
}

Note the boilerplate needed. There is no general way to do "memcpy" in Solidity (lack of sizeof and a EVM opcode?).

An Example

/// Monetary unit rtb function for basic particle/universal index.
function rtb(BasicParticle memory a, Time t) internal pure
    returns (Value v)
{
    return a._flow_rate.mul(t - a._settled_at) + a._settled_value;
}

/// Monetary unit settle function for basic particle/universal index.
function settle(BasicParticle memory a, Time t) internal pure
    returns (BasicParticle memory b)
{
    b = a.clone();
    b._settled_value = rtb(a, t);
    b._settled_at = t;
}

Tests Generation With Function Pointers

Define the Test Generator

function run_uu_test(uint16 m1, int64 x1, uint16 m2, int64 x2, uint16 m3,
                     function (BasicParticle memory, BasicParticle memory, Time, int64)
                         internal pure
                         returns (BasicParticle memory, BasicParticle memory) op1,
                     function (BasicParticle memory, BasicParticle memory, Time, int64)
                         internal pure
                         returns (BasicParticle memory, BasicParticle memory) op2
                    ) internal {
    UU_Test_Data memory d;
    d.t1 = Time.wrap(m1);
    d.t2 = d.t1 + Time.wrap(m2);
    d.t3 = d.t2 + Time.wrap(m3);

    (d.a, d.b) = op1(d.a, d.b, d.t1, x1);
    (d.a, d.b) = op2(d.a, d.b, d.t2, x2);
    assertEq(0, Value.unwrap(d.a.rtb(d.t3) + d.b.rtb(d.t3)));
}

Generate Tests

function test_uu_ss(uint16 m1, int64 x1, uint16 m2, int64 x2, uint16 m3) external {
    run_uu_test(m1, x1, m2, x2, m3, uu_shift2, uu_shift2);
}
function test_uu_ff(uint16 m1, int64 r1, uint16 m2, int64 r2, uint16 m3) external {
    run_uu_test(m1, r1, m2, r2, m3, uu_flow2, uu_flow2);
}
function test_uu_fs(uint16 m1, int64 r1, uint16 m2, int64 x2, uint16 m3) external {
    run_uu_test(m1, r1, m2, x2, m3, uu_flow2, uu_shift2);
}
function test_uu_sf(uint16 m1, int64 x1, uint16 m2, int64 r2, uint16 m3) external {
    run_uu_test(m1, x1, m2, r2, m3, uu_shift2, uu_flow2);
}

A Play Book

Define Data

/**
 * @title Basic particle: the building block for payment primitives.
 */
struct BasicParticle {
    Time     _settled_at;
    FlowRate _flow_rate;
    Value    _settled_value;
}

/// Pure data clone function.
function clone(BasicParticle memory a ) internal pure
    returns (BasicParticle memory b)
{
    // TODO memcpy
    b._settled_at = a._settled_at;
    b._flow_rate = a._flow_rate;
    b._settled_value = a._settled_value;
}

Create "Strictly" Pure Functions for the Data

function shift1(BasicParticle memory a, Value x) internal pure
    returns (BasicParticle memory b)
{
    b = a.clone();
    b._settled_value = b._settled_value + x;
}

function flow1(BasicParticle memory a, FlowRate r) internal pure
    returns (BasicParticle memory b)
{
    b = a.clone();
    b._flow_rate = r;
}

Find Properties and Write Tests for These Functions

  • Mathematical laws that governs how these functions should work together.
  • Tested through property testing, e.g. foundry fuzzing testing framework

Example 1: settle idempotence

\[ a.settle(t1).settled\_at() = t1 \] \[ a.settle(t1).settle(t1) = a.settle(t1) \] 

function test_u_settle_idempotence(BasicParticle memory p, uint16 m) external {
    limitToSafeParticle(p);

    Time t1 = p.settled_at() + Time.wrap(m);
    BasicParticle memory p1 = p.settle(t1);
    BasicParticle memory p2 = p1.settle(t1);
    assertEq(p1.settled_at(), t1, "e1");
    assertEq(p1, p2, "e2");
}

Example 2: Monoid Associativity Laws

\[ (a \times b) \times c = a \times (b \times c) \] 

function test_u_monoid_assoc(BasicParticle memory p1, BasicParticle memory p2, BasicParticle memory p3) external {
    limitToSafeParticle(p1);
    limitToSafeParticle(p2);
    limitToSafeParticle(p3);
    assertEq(p1.mappend(p2).mappend(p3), p1.mappend(p2.mappend(p3)), "e2");
}

Stitching Things Together Using Side Effects

The M-Word

  • No one has managed to explain what is a monad.

    what-is-monad.png

  • But one use case can be:
    • "Monad" as a Highly Reusable Code for Side Effects

Use Abstract Contract

A way to emulate the concept of Monad in Solidity.

Use Abstract Contract (1) - Virtual Functions

Use Virtual functions deferring the implementations of side effects: 

abstract contract TokenMonad {
    function _getUIndex(bytes memory eff, address owner)
        virtual internal view returns (BasicParticle memory);
    function _setUIndex(bytes memory eff, address owner, BasicParticle memory p)
        virtual internal returns (bytes memory);
}

Use Abstract Contract (2) - Effectful function

function _doFlow(bytes memory eff,
                 address from, address to, bytes32 flowHash, FlowRate flowRate,
                 Time t)
    internal returns (bytes memory)
{
    if (from == to) return eff; // short circuit
    // retrieving data
    FlowRate flowRateDelta = flowRate - _getFlowRate(eff, flowHash);
    BasicParticle memory a = _getUIndex(eff, from);
    BasicParticle memory b = _getUIndex(eff, to);

    // applying data transformations
    (a, b) = a.shift_flow2b(b, flowRateDelta, t);

    // applying updating side effects
    eff = _setUIndex(eff, from, a);
    eff = _setUIndex(eff, to, b);
    eff = _setFlowInfo(eff, flowHash, from, to, flowRate, flowRateDelta);

    return eff;
}

Recap

  • Define data
  • Strictly pure functions for the data.
  • Find properties and write tests for them.
  • Stitching things together with strict separation of pure functions and side effects.

Can I Do It In Production?

Yes. In Superfluid.

  • SuperToken v1 for EVM uses this for the upcoming new feature GDA (one to many streaming of money).
  • SuperToken v2 for Starknet prototype is using this pattern to, although in Cairo v0 (…).
  • SuperToken v2 for EVM will be built from scratch using this paradigm.

Teaser: Can We Use Solidity/Yul Instead?

Not directly, but to use another higher level functional programming language to transpire to it?

Thank you for listening!

Let's Make Solidity Code Better Using Functional Programming Now!!

Transcript available from github-wiki:superfluid-finance/protocol-monorepo. download-from-github-wiki.png