CSE271: Principles of Programming Languages

Dealing with the Infinite

Jooyong Yi (UNIST)

Interpreter

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

Interpreter

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

• How many programs can an interpreter handle?

Interpreter

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

• How many programs can an interpreter handle?
• Do we need infinite number of "ingredients" to write infinite number of programs?

Tiny Language

 Exp: Num | Exp + Exp

Tiny Language

Exp: Num | Exp + Exp

• How many expressions can you write in this language?

Tiny Language

Exp: Num | Exp + Exp

• How many expressions can you write in this language?
• How can we write infinite number of expressions using finite number of "ingredients"?

Inductive Definition

Let's consider set S defined as follows:

Given a natural number n, n ∈ S if and only if

1. n = 0 or
2. n - 3 ∈ S

• Consider {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...}. Which elements are in S?

Inductive Definition

Given a natural number n, n ∈ S if and only if

1. n = 0 or
2. n - 3 ∈ S

• How many elements are in S?
• How many "ingredients" (rules) do we use to define S?

Inductive Definition (Top-Down)

Given a natural number n, n ∈ S if and only if

1. n = 0 or
2. n - 3 ∈ S

Inductive Definition (Bottom-Up)

Define the set S to be the smallest set such that

1. 0 ∈ S, and
2. If n ∈ S, then n + 3 ∈ S

Inductive Definition (Bottom-Up)

Define the set S to be the *smallest* set such that

1. 0 ∈ S, and
2. If n ∈ S, then n + 3 ∈ S

• There is one set that satisfies the definition. What is it?

Inductive Definition (Bottom-Up; Rule-Inference)

Define the set S to be the *smallest* set such that

1. 0 ∈ S, and
2. If n ∈ S, then n + 3 ∈ S

[Rule 1 (Axiom)]

--------------
   0 ∈ S


[Rule 2]

   n ∈ S            hypothesis (antecedent)
--------------
  n + 3 ∈ S         conclusion (consequent)

Tiny Language

Exp: Num | Exp + Exp

--------------
   Num ∈ Exp


  E1 ∈ Exp    E2 ∈ Exp
-----------------------
     E1 + E2 ∈ Exp     

List of Integers (Bottom-Up)

Define the set List-of-Int to be the *smallest* set such that

1. () ∈ List-of-Int, and
2. If n ∈ Int and l ∈ List-of-Int, then (n . l) ∈ List-of-Int

List of Integers (Rule-Inference)

() ∈ List-of-Int


n ∈ Int          l ∈ List-of-Int
--------------------------------
  (n . l) ∈ List-of-Int

List of Integers (Top-Down)

Given a list l, l ∈ List-of-Int if and only if

1. l = () or
2. The head of l is an integer and the tail of l is in List-of-Int

List of Integers (Grammar)

() ∈ List-of-Int


n ∈ Int          l ∈ List-of-Int
--------------------------------
  (n . l) ∈ List-of-Int

List-of-Int::= () | (Int . List-of-Int)

Interpreter

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

• To the interpreter, P is data, which is inductively defined.

Interpreter

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

• To the interpreter, P is data, which is inductively defined.
• An interpreter is a program that can handle inductively defined data.

How to handle inductively-defined data?

list-length

> (length '(1 2 3))
3

> (length '())
0

list-length

• contract: list-length: List -> Int

(define list-length
  (lambda (lst)
   ...))

list-length

List-of-Int::= () | (Int . List-of-Int)

(define list-length
  (lambda (lst)
   ...))

list-length

List-of-Int::= () | (Int . List-of-Int)

(define list-length
  (lambda (lst)
    (if (null? lst)
        0
        ...)))

list-length

List-of-Int::= () | (Int . List-of-Int)

(define list-length
  (lambda (lst)
    (if (null? lst)
        0
        (+ 1 (list-length (cdr lst))))))

• cdr is a function that returns the tail of a list.
• car is a function that returns the head of a list.
• Why are they called car and cdr? see here

nth-element

> (nth-element '(a b c) 0)
a

> (nth-element '(a b c) 1)
b

nth-element

• contract: nth-element: List[T] × Int -> T

(define nth-element
  (lambda (lst n)
   ...))

nth-element

(define nth-element
  (lambda (lst n)
    (if (zero? n)
        (car lst)
        ...)))

nth-element

(define nth-element
  (lambda (lst n)
    (if (zero? n)
        (car lst)
        (nth-element (cdr lst) (- n 1)))))

nth-element

(define nth-element
  (lambda (lst n)
    (if (null? lst)
        ... ; error
        (if (zero? n)
        (car lst)
        (nth-element (cdr lst) (- n 1))))))