Zulip Chat Archive

Stream: lean4

Topic: Telescope action on binders/let values


Arthur Adjedj (Jan 08 2024 at 15:01):

Hi. Currently, functions like forallTelescope and lambdaTelescope are useful in that they allow one to traverse terms easily, but don't allow the user to i.e influence the values/types of variables added in the local context.
Take for example the following function in Lean.Meta.Reduce, which is used to elaborate the #reduce command:

partial def reduce (e : Expr) (explicitOnly skipTypes skipProofs := true) : MetaM Expr :=
  let rec visit (e : Expr) : MonadCacheT Expr Expr MetaM Expr :=
    checkCache e fun _ => Core.withIncRecDepth do
      if ( (pure skipTypes <&&> isType e)) then
        return e
      else if ( (pure skipProofs <&&> isProof e)) then
        return e
      else
        let e  whnf e
        match e with
        | Expr.app .. =>
          let f      visit e.getAppFn
          let nargs := e.getAppNumArgs
          let finfo  getFunInfoNArgs f nargs
          let mut args  := e.getAppArgs
          for i in [:args.size] do
            if i < finfo.paramInfo.size then
              let info := finfo.paramInfo[i]!
              if !explicitOnly || info.isExplicit then
                args  args.modifyM i visit
            else
              args  args.modifyM i visit
          if f.isConstOf ``Nat.succ && args.size == 1 && args[0]!.isNatLit then
            return mkRawNatLit (args[0]!.natLit?.get! + 1)
          else
            return mkAppN f args
        | Expr.lam ..        => lambdaTelescope e fun xs b => do mkLambdaFVars xs ( visit b)
        | Expr.forallE ..    => forallTelescope e fun xs b => do mkForallFVars xs ( visit b)
        | Expr.proj n i s .. => return mkProj n i ( visit s)
        | _                  => return e
  visit e |>.run

This function visits and reduces every redex. However, it doesn't reduce binder types. For example, #reduce (x : id Nat) -> Fin x doesn't reduce id Nat. My initial attempt at fixing such things has been to manipulate the local context during the traversal, by overwriting variables to the local context and modifying their types/values, as such:

forallTelescope e fun xs b => do
  let mut lctx  getLCtx
  for e in xs do
    let some lcdl := lctx.findFVar? e | unreachable!
    let value  withReader (fun ctx => {ctx with lctx := lctx})
      (visit lcdl.value)
    lctx := LocalContext.addDecl lctx (lcdl.setValue value)
  withReader (fun ctx => {ctx with lctx := lctx})
    (mkForallFVars xs ( visit b))

but this doesn't look elegant nor efficient to me. Is there any nice way to do something like this, apart from writing separate telescope functions ?

Arthur Adjedj (Jan 08 2024 at 15:06):

This is one example where I've encountered the need to do such a thing, a second one, which occurred to me now, happens here: the let declarations' bodies don't get reduced before being added to the local context, leading to some metavariables not getting assigned. Fixing this resolves #3146


Last updated: May 02 2025 at 03:31 UTC