# Project ideas

## TIO
[TIO](https://git.science.uu.nl/4110161/tio#) is a brand new Haskell security library:
- Formalize and establish the security guarantees of TIO (or find holes and patch them)
- Build a secure application to evaluate TIO. This will likely require designing new extensions (eg exceptions, mutable state, concurrency).

## [MicroHS](https://hackage.haskell.org/package/MicroHs)
* Verify that the SKI to Wasm pass in our [MicroHS' WasmGC backend](https://git.science.uu.nl/MartijnCBV/MicroHs/tree/wasmgc) is correct.
* Extend the backend to sandbox full applications (e.g., [Haskell Playground](https://blog.haskell.org/the-haskell-playground/), [pandoc](https://hackage.haskell.org/package/pandoc), [shellcheck](https://github.com/koalaman/shellcheck)).

## WebAssembly
* Develop well-typed Wasm code generators, or type-preserving wasm-to-wasm optimizations
* Implement and verify a [Wasm compiler](https://studenttheses.uu.nl/bitstream/handle/20.500.12932/46861/LeanWasm.pdf?sequence=1&isAllowed=y)
* Derive verified validators from [SpecTec](https://webassembly.org/news/2025-03-27-spectec/)

## Constant time
* Sharing pixels between applications can lead to [data leaks](https://www.pixnapping.com). Design a window manager to prevent pixel stealing attacks.

## Program analysis
Implement a program analysis:
* To find vulnerabilities in an unsafe language (eg use-after-free or buffer overflows), or
* As part of the implementation of a safe language (like Rust's borrow checker).

Implement the analysis on a (simplified) existing language like C, Java, Haskell (or GHC Core) or LLVM IR, or on a toy language. You may use type and effect systems, or use a different analysis strategy (for instance, monotone frameworks) if that better suits your analysis or language.

## Design and implement (lock-free) concurrency primitives.
* If you have enough experience with Rust: implement Haskell's MVar in Rust (with fairness!).
* If you have some experience with concurrent algorithms: Implement a method to limit the number of threads for concurrent data structures.
    * Some concurrent primitives (like our [atomic reference counting solution](https://research-portal.uu.nl/ws/portalfiles/portal/239226614/978-3-031-69583-4_8.pdf)) can operate wait-free (guaranteed progress for all threads) if there are at most $P$ threads.
    * These primitives are unsound if there are more than $P$ threads, and should thus be marked 'unsafe' in Rust.
    * For this project, implement and benchmark a safe and efficient method to let the first $P$ threads work in the wait-free mode, and let other threads switch to a lock-free mode.
    * Talk to Ivo for more info.

## Improve Iterators
Iterators in Rust provide an elegant way to write safe traversals of data. Extend their functionality, for instance with an option to let them run in-place.
  * In Rust, you for instance cannot write `foo.iter().filter(|x| *x % 2 == 0).collect_into(&mut foo);` as you borrow `foo` twice,
    even though you could write something similar in a regular for loop. Design an interface to safely perform in-place updates in iterators.
  * In Rust, you cannot elegantly express horizontal fusion in an iterator. If two operations depend on a single input, you would need to traverse the input twice,
    whereas in an imperative loop you could combine these in a single traversal. Design an interface that allows you to express horizontal fusion (and/or
    other ways of combining multiple operation into a single traversal of a data structure).

## Improve Bounds Analysis in Accelerate
The compiler of Accelerate, a DSL for parallel array programming, performs bounds analysis: an analysis that tries to prove whether array indexing is within the bounds of an array. The goal of this project is to improve the accuracy of the analysis.
For instance, we currently don't analyze operations that could cause integer overflow. As an improvement, we could track those if we can prove that they won't overflow.
You should have followed Advanced Functional Programming for this project. Talk to Ivo before you choose this topic.

<!-- Markdeep: -->
<style class="fallback">body{visibility:hidden;white-space:pre;font-family:monospace}</style><script src="markdeep.min.js"></script>
<script src="https://morgan3d.github.io/markdeep/latest/markdeep.min.js"
        charset="utf-8"></script>
<script>
  window.alreadyProcessedMarkdeep || (document.body.style.visibility="visible");
</script>