<div dir="ltr">Hi,<div><br></div><div>AFAIK, if you first define a renaming operation recursively, and then define substitution as a separate operation, then everything is clearly structural and sizes are unnecessary. You may want to use sized terms for a different reason though. I personally haven't yet found a need for sized terms when formalizing lambda calculi. </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Georgi Lyubenov <<a href="mailto:godzbanebane@gmail.com">godzbanebane@gmail.com</a>> ezt írta (időpont: 2020. márc. 24., K, 23:28):<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hello!<br><br>Sorry if this isn't the right place to ask a question like this!<br><br>I want to express named lambda terms in Agda. By doing so in the most "naive" way possible, I encounter a termination issue when implementing substitution - when I want to rename a variable to avoid accidental variable capture, the termination checker is unhappy - I'm trying to do a recursive call (recursive calling substitution) on the result of a function (renaming). My first thought is to attach sizes (via either Nats or the builtin Size type), and show that renaming doesn't "change size". After a bit of struggling I couldn't manage to do so, and am writing to ask for a hint or some advice.<br> <br>This is my initial attempt:<br><br><div>data : Size -> Set where<br>  v : {i : Size} -> (n : Nat) -> Lambda i<br>  _app_ : {i j : Size} -> Lambda i -> Lambda j -> Lambda (sizeSuc (sizeMax i j))<br>  lam_>_ : {i : Size} -> Nat -> Lambda i -> Lambda (sizeSuc i)<br><br>but with this I can't even implement something like<br><br>promo : {i j : Size} -> Lambda i -> Lambda (sizeMax i j)<br><br>Furthermore I have no idea what return type to even give to substitution!<br><br>I am pretty sure I am missing something very fundamental about sizes and how to use them, but I couldn't find materials to answer my question.<br><br>Thanks in advance!<br><br>=======<br>Georgi</div></div>
_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se" target="_blank">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" rel="noreferrer" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br>
</blockquote></div>