Unrolling loops with helper functions
- 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