Zulip Chat Archive

Stream: lean4

Topic: Having trouble automatically showing function terminates


Ben (Sep 17 2023 at 10:52):

I have the following. The definition Expression.specialize is throwing fail to show termination ... using structural recursion

inductive Placeholder where
| x : Placeholder
| y : Placeholder
| z : Placeholder
deriving BEq

inductive Expression where
  | call (on: Expression) (arg: Expression) : Expression
  | function (param: Placeholder) (body: Expression) : Expression
  | unit (value: Placeholder) : Expression

def Expression.specialize (on: Expression) (arg: Placeholder × Expression) : Expression := match on with
| unit v => if v == arg.fst then arg.snd else unit v
| function p b => function p (b.specialize arg)
| call on arg2 =>
  let ons := on.specialize arg
  let args := arg2.specialize arg
  match ons with
  -- Offending statement
  | function p sb => sb.specialize (p, args)
  | on => Expression.call on args

Is there a example application where this infinitely recurses? Maybe just a fail of the automatic termination thing, if so is there a simple way to show it does terminate?

Scott Morrison (Sep 17 2023 at 12:03):

It's the sb.specialize call that is not obvious, and I think you should expect that to require a non-automatic proof.


Last updated: Dec 20 2023 at 11:08 UTC