7
$\begingroup$

The Agda user manual says:

This is the old way of coinduction support in Agda. You are advised to use Coinductive Records instead.

And an excellent answer on this site says:

Musical notation: This is an "old" way of doing things in Agda. It marks delayed computations with a special ∞ modality, and uses ♭ and ♯ operators to go between ∞T and T. It's not recommended anymore.

To me it seems musical notation provided a more flexible way of programming compared to having to define coinductive records manually.

Why is it not recommended any more?

Are there any pitfalls I should be aware of when reading old code that uses musical notation?

$\endgroup$
1
  • $\begingroup$ On the old Agda documentation page I found a broken link to a mailing list thread; it was possibly this one: lists.chalmers.se/pipermail/agda/2011/003337.html. That sheds a bit of light on this question, but it is not very easy to follow for me. $\endgroup$ Commented Jan 13, 2025 at 16:24

1 Answer 1

5
$\begingroup$

Musical notation is too simplistic. If we think about recursive types in terms of explicit fixpoint operators $\mu$ and $\nu$, musical notation only allows us to define types with a $\nu$ outside. They cannot express types of the form $\mu X. \nu Y. F X Y$, an emblematic example being the type of well-founded infinitary trees:

data Tree : Set where
  Node : Stream Tree -> Tree
  Leaf : Tree

This limitation is discussed in this paper mentioned at the very end of the thread you cited.

If you define Stream using musical notation

data Stream (A : Set) : Set where
  _∷_ : A → ∞ (Stream A) → Stream A

Then the following non-well-founded tree is accepted, where all children except the first one are tree itself:

tree : Tree
trees : Stream Tree

tree = Node (Leaf ∷ ♯ trees)
trees = tree ∷ ♯ trees

A similar attempt using coinductive records will be rejected:

record Stream (A : Set) : Set where
  coinductive
  field
    hd : A
    tl : Stream A
tree : Tree
trees : Stream Tree

tree = Node trees

hd trees = tree
tl trees = trees

{-
Error:
Termination checking failed for the following functions:
  tree, trees
-}

The difference is whether to allow recursive stream definitions where the stream occurs in one of the heads, as opposed to only as a tail. That is, recursive definitions of this form:

s = (... s ...) ∷ ...

With musical notation, a recursive call can occur anywhere as long as it is guarded by . It's simple, but leads to this lack of expressiveness. Roughly speaking, as soon as a type contains a coinductive type, it becomes coinductive as well, with surprising results.

With coinductive records, guarded recursion is only enabled for functions that produce a coinductive type, and then recursive calls are only allowed in the recursive fields of that coinductive type. A stream can only be used recursively in its tail, not in its head, unless it's part of another coinductive type that is nested in a stream, like this:

record Cotree : Set where
  coinductive
  field
    chld : Stream Cotree

open Cotree

cotree : Cotree
cotrees : Stream Cotree

chld cotree = cotrees

hd cotrees = cotree
tl cotrees = cotrees 

in which case cotrees is not actually recursing through its head. It can be viewed as nested recursion, where each call to cotree generates a fresh cotrees that calls itself as its tail, not its head.

chld cotree = cotrees  -- non-recursive call to auxiliary cotrees
  where
    hd cotrees = cotree
    tl cotrees = cotrees

Complete code:

{-# OPTIONS --guardedness #-}
module A where

module Musical where
  open import Codata.Musical.Notation
  open import Data.Unit

  data Stream (A : Set) : Set where
    _∷_ : A → ∞ (Stream A) → Stream A

  -- This is actually coinductive (more like Cotree below than the other Tree)
  data Tree : Set where
    Node : Stream Tree -> Tree
    Leaf : Tree

  tree : Tree
  trees : Stream Tree

  tree = Node (Leaf ∷ ♯ trees)
  trees = tree ∷ ♯ trees

record Stream (A : Set) : Set where
  coinductive
  field
    hd : A
    tl : Stream A

open Stream

data Tree : Set where
  Leaf : Tree
  Node : Stream Tree → Tree

tree : Tree
trees : Stream Tree

tree = Node trees

hd trees = tree
tl trees = trees

record Cotree : Set where
  coinductive
  field
    chld : Stream Cotree

open Cotree

cotree : Cotree
cotrees : Stream Cotree

chld cotree = cotrees

hd cotrees = cotree
tl cotrees = cotrees 
```
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.