.. :: module language.syntactic-sugar where open import Agda.Primitive open import Agda.Builtin.Bool open import Agda.Builtin.Nat open import Agda.Builtin.List open import Agda.Builtin.Equality open import Agda.Builtin.String _++_ : {A : Type} → List A → List A → List A [] ++ ys = ys (x ∷ xs) ++ ys = x ∷ (xs ++ ys) concatMap : {A B : Type} → (A → List B) → List A → List B concatMap f [] = [] concatMap f (x ∷ xs) = f x ++ concatMap f xs data Either (A B : Type) : Type where left : A → Either A B right : B → Either A B record Applicative (F : Type → Type) : Type₁ where field pure : ∀ {A} → A → F A _<*>_ : ∀ {A B} → F (A → B) → F A → F B open Applicative {{...}} record Monad (M : Type → Type) : Type₁ where field _>>=_ : ∀ {A B} → M A → (A → M B) → M B overlap {{super}} : Applicative M open Monad {{...}} instance ApplicativeList : Applicative List pure {{ApplicativeList}} = _∷ [] _<*>_ {{ApplicativeList}} fs xs = concatMap (λ f → concatMap (λ x → f x ∷ []) xs) fs MonadList : Monad List _>>=_ {{MonadList}} xs f = concatMap f xs ApplicativeEither : ∀ {Err} → Applicative (Either Err) pure {{ApplicativeEither}} = right _<*>_ {{ApplicativeEither}} (left err) _ = left err _<*>_ {{ApplicativeEither}} (right f) (left err) = left err _<*>_ {{ApplicativeEither}} (right f) (right x) = right (f x) MonadEither : ∀ {Err} → Monad (Either Err) _>>=_ {{MonadEither}} (left e) f = left e _>>=_ {{MonadEither}} (right x) f = f x .. _syntactic-sugar: *************** Syntactic Sugar *************** .. _hidden_argument_puns: Hidden argument puns ==================== If the option :option:`--hidden-argument-puns` is used, then the pattern ``{x}`` is interpreted as ``{x = x}``, and the pattern ``⦃ x ⦄`` is interpreted as ``⦃ x = x ⦄``. Here ``x`` must be an unqualified name that does not refer to a constructor that is in scope: if ``x`` is qualified, then the pattern is not interpreted as a pun, and if ``x`` is unqualified and refers to a constructor that is in scope, then the code is rejected. Note that ``{(x)}`` and ``⦃ (x) ⦄`` are not interpreted as puns. Note also that ``{x}`` is not interpreted as a pun in ``λ {x} → …`` or ``syntax f {x} = …``. However, ``{x}`` is interpreted as a pun in ``λ (c {x}) → …``. .. _do-notation: Do-notation =========== A *do-block* consists of the :ref:`layout keyword ` ``do`` followed by a sequence of *do-statements*, where .. code-block:: text do-stmt ::= pat ← expr [where lam-clauses] | let decls | expr lam-clause ::= pat → expr The ``where`` clause of a bind is used to handle the cases not matched by the pattern left of the arrow. See :ref:`details below `. .. note:: Arrows can use either unicode (``←``/``→``) or ASCII (``<-``/``->``) variants. For example:: filter : {A : Type} → (A → Bool) → List A → List A filter p xs = do x ← xs true ← p x ∷ [] where false → [] x ∷ [] Do-notation is desugared before scope checking and is translated into calls to ``_>>=_`` and ``_>>_``, which can be arbitrary user-defined functions. This means that do-blocks are not tied to any particular notion of monad. In fact, if there are no monadic statements in the do block, it can be used as sugar for a ``let``:: pure-do : Nat → Nat pure-do n = do let p2 : _ → _ p2 m = m * m p4 : _ → _ p4 m = p2 (p2 m) p4 n check-pure-do : pure-do 5 ≡ 625 check-pure-do = refl The operators used for desugaring ``do`` notation are resolved as if the user had written the desugared version, and so will refer to whatever functions are in scope by those names. To control this, the ``do`` keyword may appear qualified by a *module* name, in which case the operators will be drawn from that module instead:: module Add where _>>_ : Nat → Nat → Nat x >> y = x + y qualified-example : Nat qualified-example = Add.do 1 2 3 _ : qualified-example ≡ 6 _ = refl Note that the qualifying module is **not** opened in the scope of the ``do`` expression, i.e. no bindings are brought into scope. This means that explicit usage of ``_>>=_`` and ``_>>_`` inside a qualified ``do`` expression will still refer to the **unqualified** versions. .. _do-desugaring: Desugaring ---------- +---------------+----------------------+----------------------+ | Statement | Sugar | Desugars to | +===============+======================+======================+ | Simple bind | :: | :: | | | | | | | do x ← m | m >>= λ x → | | | m' | m' | +---------------+----------------------+----------------------+ | Pattern bind | :: | :: | | | | | | | do p ← m | m >>= λ where | | | where pᵢ → mᵢ | p → m' | | | m' | pᵢ → mᵢ | +---------------+----------------------+----------------------+ | Absurd match | :: | :: | | | | | | | do () ← m | m >>= λ () | +---------------+----------------------+----------------------+ | Non-binding | :: | :: | | statement | | | | | do m | m >> | | | m' | m' | +---------------+----------------------+----------------------+ | Let | :: | :: | | | | | | | do let ds | let ds in | | | m' | m' | +---------------+----------------------+----------------------+ If the pattern in the bind is exhaustive, the where-clause can be omitted. Example ------- Do-notation becomes quite powerful together with pattern matching on indexed data. As an example, let us write a correct-by-construction type checker for simply typed λ-calculus. First we define the raw terms, using de Bruijn indices for variables and explicit type annotations on the lambda:: infixr 6 _=>_ data Ty : Type where nat : Ty _=>_ : (A B : Ty) → Ty data Raw : Type where var : (x : Nat) → Raw lit : (n : Nat) → Raw suc : Raw app : (s t : Raw) → Raw lam : (A : Ty) (t : Raw) → Raw Next up, well-typed terms:: Context = List Ty -- A proof of x ∈ xs is the index into xs where x is located. infix 2 _∈_ data _∈_ {A : Type} (x : A) : List A → Type where zero : ∀ {xs} → x ∈ x ∷ xs suc : ∀ {y xs} → x ∈ xs → x ∈ y ∷ xs data Term (Γ : Context) : Ty → Type where var : ∀ {A} (x : A ∈ Γ) → Term Γ A lit : (n : Nat) → Term Γ nat suc : Term Γ (nat => nat) app : ∀ {A B} (s : Term Γ (A => B)) (t : Term Γ A) → Term Γ B lam : ∀ A {B} (t : Term (A ∷ Γ) B) → Term Γ (A => B) Given a well-typed term we can mechanically erase all the type information (except the annotation on the lambda) to get the corresponding raw term:: rawIndex : ∀ {A} {x : A} {xs} → x ∈ xs → Nat rawIndex zero = zero rawIndex (suc i) = suc (rawIndex i) eraseTypes : ∀ {Γ A} → Term Γ A → Raw eraseTypes (var x) = var (rawIndex x) eraseTypes (lit n) = lit n eraseTypes suc = suc eraseTypes (app s t) = app (eraseTypes s) (eraseTypes t) eraseTypes (lam A t) = lam A (eraseTypes t) Now we're ready to write the type checker. The goal is to have a function that takes a raw term and either fails with a type error, or returns a well-typed term that erases to the raw term it started with. First, lets define the return type. It's parameterised by a context and the raw term to be checked:: data WellTyped Γ e : Type where ok : (A : Ty) (t : Term Γ A) → eraseTypes t ≡ e → WellTyped Γ e We're going to need a corresponding type for variables:: data InScope Γ n : Type where ok : (A : Ty) (i : A ∈ Γ) → rawIndex i ≡ n → InScope Γ n Lets also have a type synonym for the case when the erasure proof is ``refl``:: infix 2 _ofType_ pattern _ofType_ x A = ok A x refl Since this is a do-notation example we had better have a monad. Lets use the either monad with string errors:: TC : Type → Type TC A = Either String A typeError : ∀ {A} → String → TC A typeError = left For the monad operations, we are using :ref:`instance arguments ` to infer which monad is being used. We are going to need to compare types for equality. This is our first opportunity to take advantage of pattern matching binds:: _=?=_ : (A B : Ty) → TC (A ≡ B) nat =?= nat = pure refl nat =?= (_ => _) = typeError "type mismatch: expected nat, got _ => _" (_ => _) =?= nat = typeError "type mismatch: expected _ => _, got nat" (A => B) =?= (A₁ => B₁) = do refl ← A =?= A₁ refl ← B =?= B₁ pure refl We will also need to look up variables in the context:: lookupVar : ∀ Γ n → TC (InScope Γ n) lookupVar [] n = typeError "variable out of scope" lookupVar (A ∷ Γ) zero = pure (zero ofType A) lookupVar (A ∷ Γ) (suc n) = do i ofType B ← lookupVar Γ n pure (suc i ofType B) Note how the proof obligation that the well-typed deBruijn index erases to the given raw index is taken care of completely under the hood (in this case by the ``refl`` pattern in the ``ofType`` synonym). Finally we are ready to implement the actual type checker:: infer : ∀ Γ e → TC (WellTyped Γ e) infer Γ (var x) = do i ofType A ← lookupVar Γ x pure (var i ofType A) infer Γ (lit n) = pure (lit n ofType nat) infer Γ suc = pure (suc ofType nat => nat) infer Γ (app e e₁) = do s ofType A => B ← infer Γ e where _ ofType nat → typeError "numbers cannot be applied to arguments" t ofType A₁ ← infer Γ e₁ refl ← A =?= A₁ pure (app s t ofType B) infer Γ (lam A e) = do t ofType B ← infer (A ∷ Γ) e pure (lam A t ofType A => B) In the ``app`` case we use a where-clause to handle the error case when the function to be applied is well-typed, but does not have a function type. .. _idiom-brackets: Idiom brackets ============== Idiom brackets is a notation used to make it more convenient to work with applicative functors, i.e. functors ``F`` equipped with two operations .. code-block:: agda pure : ∀ {A} → A → F A _<*>_ : ∀ {A B} → F (A → B) → F A → F B Name resolution for idiom brackets works as for ``do``-notation: the operators are resolved as though the user had written them, unless the brackets appear qualified, in which case they are looked up in the qualifying module. The syntax for idiom brackets is .. code-block:: agda (| e a₁ .. aₙ |) or using unicode lens brackets ``⦇`` (U+2987) and ``⦈`` (U+2988): .. code-block:: agda ⦇ e a₁ .. aₙ ⦈ This expands to (assuming left associative ``_<*>_``) .. code-block:: agda pure e <*> a₁ <*> .. <*> aₙ Idiom brackets work well with operators, for instance .. code-block:: agda (| if a then b else c |) desugars to .. code-block:: agda pure if_then_else_ <*> a <*> b <*> c Idiom brackets also support none or multiple applications. If the applicative functor has an additional binary operation .. code-block:: agda _<|>_ : ∀ {A B} → F A → F A → F A then idiom brackets support multiple applications separated by a vertical bar ``|``, i.e. .. code-block:: agda (| e₁ a₁ .. aₙ | e₂ a₁ .. aₘ | .. | eₖ a₁ .. aₗ |) which expands to (assuming right associative ``_<|>_``) .. code-block:: agda (pure e₁ <*> a₁ <*> .. <*> aₙ) <|> ((pure e₂ <*> a₁ <*> .. <*> aₘ) <|> (pure eₖ <*> a₁ <*> .. <*> aₗ)) Idiom brackets without any application ``(|)`` or ``⦇⦈`` expend to ``empty`` if .. code-block:: agda empty : ∀ {A} → F A is in scope. An applicative functor with ``empty`` and ``_<|>_`` is typically called ``Alternative``. Note that ``pure``, ``_<*>_``, and ``_<|>_`` need not be in scope to use ``(|)``. Limitations: - Binding syntax and operator sections cannot appear immediately inside idiom brackets. - The top-level application inside idiom brackets cannot include implicit applications, so .. code-block:: agda (| foo {x = e} a b |) is illegal. In case the ``e`` is pure you can write .. code-block:: agda (| (foo {x = e}) a b |) which desugars to .. code-block:: agda pure (foo {x = e}) <*> a <*> b