argotorg / argotorg/act

Unrolling loops with helper functions

Open
#3 13 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Haskell
Stars
279
Forks
51
Avg merge
17h 42m
Merged PRs (30d)
1

Description

When specifying the behaviour of functions that involves a loop, it is sometimes hard to express the post-state on a closed form. A real life example is [Pot.rpow](https://github.com/makerdao/dss/blob/master/src/pot.sol#L81), which calculates exponentials of fixed-point integers, or the [deposit function](https://github.com/ethereum/smart-contract-spec-lang/blob/bnfc/examples/deposit/deposit-spec.md#deposit) of the Eth2.0 registration contract.

Here I propose a syntax which introduces a `where` construct that I think could handle many such cases. But first, I would like to express the shortcomings of the proposal

In the general case, the result of a loop is difficult to express in a functional language. Especially if it updates storage in unstructured ways. For example, something like
```sol
for (i = 0; i < N; i++) {
assembly {
sstore(i,i)
}
}
```
seems hard to express elegantly in our current setting. However, such contracts are arguably pretty strange anyway.

But in most use cases, when the write-access of a loops aren't determined dynamically, the behaviour of the loop can be expressed as with the help of a recursive, pure function. To allow for such helper functions, I propose to add a new header, `where`, where they can be defined.

For example, the semantics of:
```sol
uint[] zeroHashes;
function zerohashN(uint256 n) {
bytes32 res = "0x0";
for (i = 0; i <= n; i++;) {
res += keccak256(res);
}
zeroHashes[n] = s;
```
is captured by:
```act
behaviour zeroHashN of Arithmetic
interface zeroHashN(uint256 n)

storage

zeroHashes[n] |-> _ => nth_hash_of(0, n)

where

nth_hash_of(h, n) = if n == 0 then h else hash(nth_hash_of(h, n - 1))
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the linked Pot.rpow and Eth2.0 deposit examples, then inspect the current Act behavior syntax and loop semantics; the issue names no repository files or tests. Compare the proposed where helper form with existing language rules. Done would require agreed syntax and semantics, implementation, and tests for recursive loop helpers.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell, solidity
Domain
blockchain, compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.