Scheme Programming Language :: substitution and variables


	substitution and variables (lambda (x) (x y)) #(struct:proc-exp (x) #(struct:app-exp #(struct:var-exp x) #(struct:var-exp y))) (x y) is an expression composed of two expressions x and y. x is an expression composed of the variable x. The parameter x is only a variable, it is not an expression. They say the lambda expression has a free variable y. Suppose we want to substitute the expression (x z) for the variable y. (lambda (x) (x y)) / [y -> (x z)] = (lambda (x0) (x y) / [x -> x0, y -> (x z)]) They say we are substituting an expression for a variable, but to me it looks like we are substituting an expression for an expression. On May 19, 3:44 am, "Marlene Miller" <marlenemil@worldnet.att.net> wrote: - Hide quoted text - > (lambda (x) (x y)) > #(struct:proc-exp (x) #(struct:app-exp #(struct:var-exp x) #(struct:var-exp > y))) > (x y) is an expression composed of two expressions x and y. x is an > expression composed of the variable x. The parameter x is only a variable, > it is not an expression. > They say the lambda expression has a free variable y. Suppose we want to > substitute the expression (x z) for the variable y. > (lambda (x) (x y)) / [y -> (x z)] = (lambda (x0) (x y) / [x -> x0, y -> (x > z)]) > They say we are substituting an expression for a variable, but to me it > looks like we are substituting an expression for an expression. y in (x y) is both a variable and an expression; exactly like how you represented it: #(struct:var-exp y). See, "var-exp" :-) Aziz,,, - Hide quoted text - "Abdulaziz Ghuloum" wrote: "Marlene Miller" wrote: > > (lambda (x) (x y)) > > #(struct:proc-exp (x) #(struct:app-exp #(struct:var-exp x) #(struct:var-exp > > y))) > > (x y) is an expression composed of two expressions x and y. x is an > > expression composed of the variable x. The parameter x is only a variable, > > it is not an expression. > > They say the lambda expression has a free variable y. Suppose we want to > > substitute the expression (x z) for the variable y. > > (lambda (x) (x y)) / [y -> (x z)] = (lambda (x0) (x y) / [x -> x0, y -> (x > > z)]) > > They say we are substituting an expression for a variable, but to me it > > looks like we are substituting an expression for an expression. > y in (x y) is both a variable and an expression; exactly like how you > represented it: #(struct:var-exp y). See, "var-exp" :-) > Aziz,,, #(struct:var-exp y) There is a constructor function from variables to expressions. var-exp is a constructor. y is a Scheme symbol. (lambda (x) (x y)) In this linear representation of the abstract syntax, whether the symbol y is a variable or the image of a variable depends on the context. - - - - - - - - - - lambda-exp -----+----- \| \| y app-exp ----+----+ \| \| var-exp var-exp \| \| x y We are substituting the expression app-exp ----+---- \| \| var-exp var-exp \| \| x z for the expression var-exp \| y - - - - - - - - - - In this substitution equation, the symbol to the left of -> is a variable, the symbol to the right is an expression. x and y (to the left) are variables and x0 (to the right) is an expression. (lambda (x) (x y)) / [y -> (x z)] = (lambda (x0) (x y) / [x -> x0, y -> (x z)]) The subsitution map is from variables to expressions, but we are substituting an expression for an expression. - - - - - - - - - - Why does Aziz,,, end with 3 commas? If only I knew the answer, I would know how to ask the question. (lambda (x) (x y)) (lambda (x) (x y)) / [y -> (x z)] = (lambda (x0) (x y) / [x -> x0, y ->(x z)]) y [y -> (x z)] = (x z) The second x0 of the first equation and the first y of the second equation confuse me, because they look like variables but they are expressions. The constructor associated with the production <expression> := <variable> maps variables to expressions. I would say, variables are not expressions. Is substitution textual manipulation following some rules? You ignore the hierchary of the abstract phrase?