Representing Program Syntax

Defining Programming Language Semantics

To write a program, you have to know how the language works.

• Semantics: The study of how the language works

• Methods: for defining program semantics:
  • Operational: rewrite step-by-step until end up with a value
  • Denotational: interpret a program in a different language
  • Equational: specify the equal programs
  • Axiomatic

Syntax? Semantics?

Defining Program Semantics

an interpreter program

Implementing an interpreter: sequence of characters ---parsing---> data structure representing program(AST) ---evaluation---> data structure representing result of evaluation ---pretty printing---> formatted output

Representing Syntax

Think in spliting the let expression to 3 parts let xx = xx in xx.

Tree like structure (AST?)

OCaml for the Win

Functional programming languages have sometimes been called "domain-specific languages for compiler writers"

Datatypes are amaing for representing complicated tree-like structures and that is exactly what a program is.

Making These Ideas Precise

Represent the OCaml program (sequence of string) (This is called concrete syntax, concrete syntax pertains to parsing).

let x = 30 in
let y =
  ( let z = 3 in z *4 )
in
y+y

to an exp value

Let("x", Int 30, Let ("y", Let("z", Int 3, Op (Var "z",Times,Int 4)), Op (Var "y" , Plus, Var "y")))

This is called an abstract syntax tree (AST).

Free vs Bound Variables

use of variables bound or free.

let x = 30 in
  x + y
(* x is bound y is free *)

match x with
  (y,z) -> y + z + w
(* x, w are free variables y, z are bound *)

this use of y is free

Implementing Renaming