CSE271: Principles of Programming Languages

Representations

Jooyong Yi (UNIST)

Interpreter

               Input to P
                   ↓
Program P → [ Interpreter ]
                   ↓
               Output of P

Lambda Calculus

• A simple yet as powerful as Turing machine

LcExp ::= Identifier
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

Lambda Calculus Example

(lambda (x) x)

Lambda Calculus Example

((lambda (x) x) 5)

Natural Numbers represented in Lambda Calculus

• Idea?

Natural Numbers represented in Lambda Calculus

• You can encode natural numbers using lambda calculus.

Natural Numbers represented in Lambda Calculus

(lambda (f) (lambda (x) x))
(lambda (f) (lambda (x) (f x)))
(lambda (f) (lambda (x) (f (f x))))

Natural Numbers represented in Lambda Calculus

(lambda (f) (lambda (x) x))
(lambda (f) (lambda (x) (f x)))
(lambda (f) (lambda (x) (f (f x))))

• Church numerals

Interpreter for Lambda Calculus

                                  Input
                                    ↓
Lambda calculus expression → [ Interpreter ]
                                    ↓
                                  Output

Analyzer for Lambda Calculus

                                Input
                                  ↓
Lambda calculus expression → [ Analyzer ]
                                  ↓
                                Output

occurs-free?

• A variable occurs free in an expression if it has some occurrence in that is not inside some lambda expression that binds the same variable.

> (occurs-free? 'x 'x)
#t
> (occurs-free? 'x 'y)
#f
> (occurs-free? 'x '(lambda (x) (x y)))
#f
> (occurs-free? 'x '(lambda (y) (x y)))
#t
> (occurs-free? 'x '((lambda (x) x) (x y)))
#t

First Implementation of occurs-free?

(define occurs-free?
  (lambda (var exp)
    (cond
      ((symbol? exp) (eqv? var exp)) ; Identifier
      ((eqv? (car exp) 'lambda)      ; (lambda (Identifier) LcExp)
       (and
        (not (eqv? var (car (car (cdr exp)))))
        (occurs-free? var (car (cdr (cdr exp))))))
      (else                          ; (LcExp LcExp)
        (or (occurs-free? var (car exp))
            (occurs-free? var (car (cdr exp))))))))      

First Implementation of occurs-free?

(define occurs-free?
  (lambda (var exp)
    (cond
      ((symbol? exp) (eqv? var exp)) ; Identifier
      ((eqv? (car exp) 'lambda)      ; (lambda (Identifier) LcExp)
       (and
        ; (not (eqv? var (car (car (cdr exp)))))
        (not (eqv? var (car (cadr exp))))
        ; (occurs-free? var (car (cdr (cdr exp))))))
        (occurs-free? var (caddr exp))))
      (else                          ; (LcExp LcExp)
        (or (occurs-free? var (car exp))
            ; (occurs-free? var (car (cdr exp))))))))
            (occurs-free? var (cadr exp)))))))      

The Nine Dots Puzzle

• Connect all nine dots with
  • four straight lines
  • without lifting the pen
  • without tracing the same line more than once

The Nine Dots Puzzle

• Connect all nine dots with
  • four straight lines
  • without lifting the pen
  • without tracing the same line more than once

Effective representation is crucial when performing any task.

S-expressions

S-exp  ::= Symbol | S-list                                                                       
S-list ::= ({S-exp}*)

> (occurs-free? 'x '(lambda (x) (x y)))                                                              
#f
> (occurs-free? 'x '(lambda (y) (x y)))
#t

(define occurs-free?                                                                                 
  (lambda (var exp)
    (cond
      ((symbol? exp) (eqv? var exp)) ; Identifier
      ((eqv? (car exp) 'lambda)      ; (lambda (Identifier) LcExp)
       (and
        (not (eqv? var (car (car (cdr exp)))))
        (occurs-free? var (car (cdr (cdr exp))))))
      (else                          ; (LcExp LcExp)
        (or (occurs-free? var (car exp))
            (occurs-free? var (car (cdr exp))))))))      

What If?

Instead of

LcExp ::= Identifier                                                                      
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

use the following?

LcExp ::= Identifier                                                                      
      ::= proc Identifier => LcExp
      ::= LcExp(LcExp)

How to implement occurs-free??

(define occurs-free?                                                                      
  (lambda (var exp)
   ...      

Abstraction

Two concrete syntaxes

LcExp ::= Identifier                                                                      
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

LcExp ::= Identifier                                                                      
      ::= proc Identifier => LcExp
      ::= LcExp(LcExp)

Abstract syntax

lc-exp ::= var-exp (var)                                                                      
       ::= lambda-exp (bound-var body)
       ::= app-exp (rator rand)

Abstract Syntax

lc-exp ::= var-exp (var)                                                                      
       ::= lambda-exp (bound-var body)
       ::= app-exp (rator rand)

(define occurs-free?                                                                                 
  (lambda (search-var exp)
    (cases lc-exp exp
      (var-exp (var) (eqv? search-var var))
      (lambda-exp (bound-var body)
        (and
         (not (eqv? search-var bound-var))
         (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
         (occurs-free? search-var rator)
         (occurs-free? search-var rand))))))

Example Run

> (occurs-free? 'x (parse-expression '((lambda (x) x) (x y))))

(define occurs-free?                                                                                 
  (lambda (search-var exp)
    (cases lc-exp exp
      (var-exp (var) (eqv? search-var var))
      (lambda-exp (bound-var body)
        (and
         (not (eqv? search-var bound-var))
         (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
         (occurs-free? search-var rator)
         (occurs-free? search-var rand))))))

Abstract Syntax Tree (AST)

> (occurs-free? 'x (parse-expression '((lambda (x) x) (x y))))

lc-exp ::= var-exp (var)                                                                      
       ::= lambda-exp (bound-var body)
       ::= app-exp (rator rand)

                   app-exp                                                                     
                  /      \                 
                rator    rand
                /          \
        lambda-exp         app-exp
          /    \             /   \
  bound-var    body       rator  rand
      |          \         /       \
      x        var-exp  var-exp  var-exp
                  |       |         |
                 var     var       var
                  |       |         |
                  x       x         y

Example Run with AST

                   app-exp                                                                     
                  /      \                 
                rator    rand
                /          \
        lambda-exp         app-exp
          /    \             /   \
  bound-var    body       rator  rand
      |          \         /       \
      x        var-exp  var-exp  var-exp
                  |       |         |
                 var     var       var
                  |       |         |
                  x       x         y

(define occurs-free?                                                                                                      
  (lambda (search-var exp)
    (cases lc-exp exp
      (var-exp (var) (eqv? search-var var))
      (lambda-exp (bound-var body)
        (and
         (not (eqv? search-var bound-var))
         (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
         (occurs-free? search-var rator)
         (occurs-free? search-var rand))))))

Parsing

                                                         app-exp           
                                                        /      \                 
                                                      rator    rand
                                                      /          \
                                              lambda-exp         app-exp
                                               /    \             /   \
((lambda (x) x) (x y)) → [ Parser ] →   bound-var    body       rator  rand
                                            |          \         /       \
                                            x        var-exp  var-exp  var-exp
                                                        |       |         |
                                                       var     var       var
                                                        |       |         |
                                                        x       x         y

Parsing

((lambda (x) x) (x y)) → [ Parser ] →   ...                                                             

LcExp ::= Identifier                                                                                  
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

lc-exp ::= var-exp (var)                                                                                    
       ::= lambda-exp (bound-var body)
       ::= app-exp (rator rand)

(define parse-expression                                                                                  
  (lambda (datum)
    (cond
      ((symbol? datum) (var-exp datum))
      ((pair? datum)
       (if (eqv? (car datum) 'lambda)
           (lambda-exp (car (cadr datum))
                       (parse-expression (caddr datum)))
           (app-exp (parse-expression (car datum))
                    (parse-expression (cadr datum)))))
      (else (report-invalid-expression datum)))))

Remarks

(define parse-expression                                                                                  
  (lambda (datum)
    (cond
      ((symbol? datum) (var-exp datum))
      ((pair? datum)
       (if (eqv? (car datum) 'lambda)
           (lambda-exp (car (cadr datum))
                       (parse-expression (caddr datum)))
           (app-exp (parse-expression (car datum))
                    (parse-expression (cadr datum)))))
      (else (report-invalid-expression datum)))))

• What is the input to parse-expression?

Remarks

(define parse-expression                                                                                  
  (lambda (datum)
    (cond
      ((symbol? datum) (var-exp datum))
      ((pair? datum)
       (if (eqv? (car datum) 'lambda)
           (lambda-exp (car (cadr datum))
                       (parse-expression (caddr datum)))
           (app-exp (parse-expression (car datum))
                    (parse-expression (cadr datum)))))
      (else (report-invalid-expression datum)))))

• What is the input to parse-expression?
  • data ≠ program?

In Denmark ...

• Computer Science is called Datalogi, which means "Data Science".

What If

Instead of

LcExp ::= Identifier                                                                      
      ::= (lambda (Identifier) LcExp)                                                                                         
      ::= (LcExp LcExp)

the following is used?

LcExp ::= Identifier                                                                      
      ::= proc Identifier => LcExp                                                                                        
      ::= LcExp(LcExp)

How to change?

(define parse-expression                                                                                                 
  (lambda (datum)
    (cond
      ((symbol? datum) (var-exp datum))
      ((pair? datum)
       (if (eqv? (car datum) 'lambda)
           (lambda-exp (car (cadr datum))
                       (parse-expression (caddr datum)))
           (app-exp (parse-expression (car datum))
                    (parse-expression (cadr datum)))))
      (else (report-invalid-expression datum)))))

Parsing

You can learn more about parsing in CSE411, Introduction to Compilers.

Pattern Matching

(define occurs-free?                                                                                 
  (lambda (search-var exp)
    (cases lc-exp exp
      (var-exp (var) (eqv? search-var var))
      (lambda-exp (bound-var body)
        (and
         (not (eqv? search-var bound-var))
         (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
         (occurs-free? search-var rator)
         (occurs-free? search-var rand))))))

lc-exp ::= var-exp (var)                                                                                    
       ::= lambda-exp (bound-var body)
       ::= app-exp (rator rand)

(cases <type-name> <expression>)                                                                      
  {(variant-name ({<field-name>}*)) <consequent>}*

Without Pattern Matching

(define occurs-free?                                                                                              
  (lambda (search-var exp)
    (cases lc-exp exp
      (var-exp (var) (eqv? search-var var))
      (lambda-exp (bound-var body)
        (and
         (not (eqv? search-var bound-var))
         (occurs-free? search-var body)))
      (app-exp (rator rand)
        (or
         (occurs-free? search-var rator)
         (occurs-free? search-var rand))))))

(define occurs-free?                                                                                             
  (lambda (search-var exp)
    (cond
      ((var-exp? exp) (eqv? search-var (var-exp->var exp)))
      ((lambda-exp? exp)
       (and
        (not (eqv? search-var (lambda-exp->bound-var exp)))
        (occurs-free? search-var (lambda-exp->body exp)))
      (else
       (or
        (occurs-free? search-var (app-exp->rator exp))
        (occurs-free? search-var (app-exp->rand exp))))))))

Operations to Handle lc-exp Expressions

(define occurs-free?                                                                                             
  (lambda (search-var exp)
    (cond
      ((var-exp? exp) (eqv? search-var (var-exp->var exp)))
      ((lambda-exp? exp)
       (and
        (not (eqv? search-var (lambda-exp->bound-var exp)))
        (occurs-free? search-var (lambda-exp->body exp)))
      (else
       (or
        (occurs-free? search-var (app-exp->rator exp))
        (occurs-free? search-var (app-exp->rand exp))))))))

• Operations: var-exp?, var-exp->var, lambda-exp?, lambda-exp->bound-var, lambda-exp->body, app-exp?, app-exp->rator, app-exp->rand

Operations to Handle lc-exp Expressions

(define occurs-free?                                                                                             
  (lambda (search-var exp)
    (cond
      ((var-exp? exp) (eqv? search-var (var-exp->var exp)))
      ((lambda-exp? exp)
       (and
        (not (eqv? search-var (lambda-exp->bound-var exp)))
        (occurs-free? search-var (lambda-exp->body exp)))
      (else
       (or
        (occurs-free? search-var (app-exp->rator exp))
        (occurs-free? search-var (app-exp->rand exp))))))))

• Operations
  • Predicates: var-exp?, lambda-exp?, app-exp?
  • Extractors: var-exp->var, lambda-exp->bound-var, lambda-exp->body, app-exp->rator, app-exp->rand

Operations to Handle lc-exp Expressions

(define parse-expression                                                                                  
  (lambda (datum)
    (cond
      ((symbol? datum) (var-exp datum))
      ((pair? datum)
       (if (eqv? (car datum) 'lambda)
           (lambda-exp (car (cadr datum))
                       (parse-expression (caddr datum)))
           (app-exp (parse-expression (car datum))
                    (parse-expression (cadr datum)))))
      (else (report-invalid-expression datum)))))

• Operations
  • Predicates: var-exp?, lambda-exp?, app-exp?
  • Extractors: var-exp->var, lambda-exp->bound-var, lambda-exp->body, app-exp->rator, app-exp->rand
  • Constructors: var-exp, lambda-exp, app-exp

Operations to Handle lc-exp Expressions

• Predicates
  • var-exp?: Lc-exp → Bool
  • lambda-exp?: Lc-exp → Bool
  • app-exp?: Lc-exp → Bool
• Extractors
  • var-exp->var: Lc-exp → Var
  • lambda-exp->bound-var: Lc-exp → Var
  • lambda-exp->body: Lc-exp → Lc-exp
  • app-exp->rator: Lc-exp → Lc-exp
  • app-exp->rand: Lc-exp → Lc-exp

Operations to Handle lc-exp Expressions

• Constructors
  • var-exp: Var → Lc-exp
  • lambda-exp: Var × Lc-exp → Lc-exp
  • app-exp: Lc-exp × Lc-exp → Lc-exp

Implementing Constructors

  ;; var-exp : Var -> Lc-exp
  (define var-exp
    (lambda (var)
      `(var-exp ,var)))

  ;; lambda-exp : Var * Lc-exp -> Lc-exp
  (define lambda-exp
    (lambda (var lc-exp)
      `(lambda-exp ,var ,lc-exp)))

  ;; app-exp : Lc-exp * Lc-exp -> Lc-exp
  (define app-exp
    (lambda (lc-exp1 lc-exp2)
      `(app-exp ,lc-exp1 ,lc-exp2)))

Implementing Predicates

;; var-exp? : Lc-exp -> Bool
(define var-exp?
  (lambda (x)
    (and (pair? x) (eqv? (car x) 'var-exp))))

;; lambda-exp? : Lc-exp -> Bool
(define lambda-exp?
  (lambda (x)
    (and (pair? x) (eqv? (car x) 'lambda-exp))))

;; app-exp? : Lc-exp -> Bool
(define app-exp?
  (lambda (x)
    (and (pair? x) (eqv? (car x) 'app-exp))))

Implementing Extractors

;; var-exp->var : Lc-exp -> Var
(define var-exp->var
  (lambda (x)
    (cadr x)))

;; lambda-exp->bound-var : Lc-exp -> Var
(define lambda-exp->bound-var
  (lambda (x)
    (cadr x)))

;; lambda-exp->body : Lc-exp -> Lc-exp
(define lambda-exp->body
  (lambda (x)
    (caddr x)))

;; app-exp->rator : Lc-exp -> Lc-exp
(define app-exp->rator
  (lambda (x)
    (cadr x)))

;; app-exp->rand : Lc-exp -> Lc-exp
(define app-exp->rand
  (lambda (x)
    (caddr x)))

What If

Instead of

LcExp ::= Identifier                                                                      
      ::= (lambda (Identifier) LcExp)                                                                                            
      ::= (LcExp LcExp)

the following is used?

LcExp ::= Identifier                                                                                  
      ::= proc Identifier => LcExp                                                                                        
      ::= LcExp(LcExp)

What to change?

(define occurs-free?                                                                                                     
  (lambda (search-var exp)
    (cond
      ((var-exp? exp) (eqv? search-var (var-exp->var exp)))
      ((lambda-exp? exp)
       (and
        (not (eqv? search-var (lambda-exp->bound-var exp)))
        (occurs-free? search-var (lambda-exp->body exp)))
      (else
       (or
        (occurs-free? search-var (app-exp->rator exp))
        (occurs-free? search-var (app-exp->rand exp))))))))

Data Abstraction

[Concrete syntax]                                [Abstract syntax]

LcExp ::= Identifier                             lc-exp ::= var-exp (var)              
      ::= (lambda (Identifier) LcExp)                   ::= lambda-exp (bound-var body)
      ::= (LcExp LcExp)                                 ::= app-exp (rator rand)

[Interface]
var-exp : Var -> Lc-exp                                                                   

[Implementation]
(define var-exp
    (lambda (var)
      `(var-exp ,var)))