Skip to content
scrambled
Programming Language Theory Flashcard

What is the usual treatment for the substitution problems (variable capture, etc.)

Question

What is the usual treatment for the substitution problems (variable capture, etc.)

Answer

Using Capture-avoiding substitution:

  • [x→s]x=s

  • [x→s]y=y if x≠y

  • [x→s](t1 t2)=[x→s]t1 [x→s]t2

  • -
[x→s]λy. t={λy. tif x=yλy. [x→s]tif x≠y∧y∉FV(s)