[Solved]: Abstract Syntax Tree of Pure Lambda Calculus

Problem Detail: 

I was wondering if anyone had any good references or book recommendations that cover abstract syntax trees (ASTs). Specifically, I am interested in the abstract syntax trees of different evaluation strategies (call by value vs. call by name) of the pure lambda calculus. I would like to be able to draw the AST of some pure lambda calculus expression such as $$and \, true \, false = (\lambda a. \lambda b. a \, b \, (\lambda t. \lambda f. f))(\lambda t. \lambda f. t)(\lambda t. \lambda f. f).$$

I would like to know if/how evaluation strategies affect the structure of ASTs, or how order of operation is reflected in the AST of an expression. This seems trivial for any pure lambda calculus interpreter; so perhaps there is some AST generator out there somewhere? I did some searching on Google but found nothing.

I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

Asked By : baffld

Answered By : Alexey Romanov

I would like to know if/how evaluation strategies affect the structure of ASTs, how order of operation is reflected in the AST of an expression

They don't, and it isn't. Evaluation strategies are functions which take ASTs as arguments, and return ASTs (or possibly only normal forms), so you can have different evaluation strategies working on the same AST.

I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

See e.g. this Stack Overflow question:

data Exp = Var String              | App Exp Exp              | Lam String Exp 

In the case of pure lambda-calculus, there is no Constant Int, and and would look like

Lam "a"    (Lam "b"       (App          (App             (Var "a")             (Var "b"))         (Lam "t"             (Lam "f"                (Var "f"))))) 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22949