CakeML / CakeML/cakeml

Add support for loops

Open
#665 0 comments 0 reactions 0 assignees View on GitHub
low priority
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

Loops can be encoded using tail-ref functions.
Yet, they are incredibly useful in the surface language.
Especially for describing algorithms.
Many graph algorithms take the form
`while not (queue.is_empty()) do let x = queue.pop() in ...done`.
In fact, there are also idiomatic programming pattern using `break` and `continue` that are pretty ugly to encode without these constructs.
A typical example is an early exit from a Dijkstra traversal, e.g.:
`... if x = target_vertex then break; ...`
Break and continue can be encoded using exception, but again that's not pretty.

Presenting formalization of algorithms to researchers in that field without a standard loop syntax is a no-go. Furthermore, there are nice high-level reasoning rules that apply to many loop patterns.

I thus encourage adding loops as well as some form of break/continue in the source language.

The compiler could either treat them directly using goto-s, or try to compile them into tail-rec functions with exceptions for break and continue, then eliminate the closure and the try-catch. Whatever is most convenient.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.