Tutorial 2026-01-28

Faux Racket

Code ------------------------> making code.

(program )

• In Onenote

• Faux Racket

  • Integer, +, -, *

expr = int list (expr expr )

1, (+ 1 2 )

( + 1 ( * 2 3 ) )

data Expr = Lit Integer

• Bin Op Expr : Expr

data Op = Add | Mult

(Bin ( Add (Lit 1 ) ( Bin Mult ) ( Lit 2 ) (lit 3 )))

With the AST we can

1. Evaluate it to an integer result ( interpreting )

2. Write a machine language program ( compiling )

interp Expr -> Integer

interp (Lit x) = x
interp (Bin Add a b) = (interp a ) + ( interp b)
interp (Bin Mult a b ) = (interp a ) * (interp b)

Alt:

optrans :: op -> ( Integer -> Integer -> Integer)
optrans Add = (+)
optrns Mult = (*)

with this we can make interpreter.

Alt: we can write in one.

interp (Bin op a b ) = ((optrans op) (interp a) (interp  ))

New Faux Racket Grammar

expr = (fun (id) expr)
   1 ( expr expr )
   1 (with (id expr ) expr )

Valid Expressions include, id, int, or (op expr expr)

((fun (x) ( + x 1 )) 2 )

Use substitution model for normal racket to simplify.

(fun (x) (fun(x)(+ x x)) 2 ) 3 ) 

What does this produce? It's pretty ambiguous rn for our language, but we see that:

Always bind variables to the innermost scope.

e.g.

(fun (x) (fun(x)(+ x x)) 2 ) 3 ) 
> (fun (x) (+ 3 3 ) 2 ) 
> 6

Data Expr = (Fun String Expr)
                | (App Expr eXPR)
                | (String, Expr) Expr)
                | (Var String)
                | (Lit Integer)
                | (Bin op Expr Expr)
-- We are defining names for our Haskall Intrepreter.

App for Application

interp Expr -> Expr
interp x@(Lit _ ) = x
-- returns x, which is pattern matched all literals.
interp x@(var _ ) = x
interp x@(Fun _ _ ) = x
interp x@(var, val) body) = (App (Fun var body) val )
-- Do you now see the power of Pattern Matching?
interp(App fn arg) = (interp (subst par (interp arg) body))
-- Where ( Fun par body) = (interp Rn )

interp ( Bin op a b) = lit(optrans ) a'b))
Where
(Lit a') = interp a 
(Lit b') = interp b

Now we write our last function, subst :

subst ::: String -> Expr -> Expr -> Expr
subst i v ( Var x) = if x == i then v else (Var x)
-- If i and x are matching replace with v, else return (Var x ) as there is nothing to replace
subst i v ( Lit x ) = (Lit x)
subst i v ( Bin op a b ) =  (Bin op ( subst i v a ) 
                                    ( subst i v b ) )
subst i v (App a b ) = (App ( subst i v a ) 
                            (subst i v b))
                            
subst i v x@(Fun par body) = if i== par then x else (Fun par (subst i v body))