8/25/21
Key topics discussed so far
Lecture 1: General ideas about PLs
Abstraction: Examples? Empowerment: Examples?
PLs need to be compiled: Why? There are many PLs: Why?
Lecture 2: Computability – TM and l-calculus We are not interested in what are computable
functions and what are not.
Instead, we ask: Can we guarantee that all computable solutions derived are runnable on a computer?
Problem with the above Q? Computability cannot be defined Why not?
12
Lecture 2: Computability – TM and l-calculus Computability cannot be defined – why not?
It depends on what effective procedure What is an is used to compute a function. effective
A method whereby each step is precisely predetermined that when executed will give you an answer in a finite number of steps
procedure?
Lecture 2: Computability – TM and l-calculus Two effective procedures have been
discovered – what are they? TM and l-calculus
TM
A state table + an infinite tape + n 1’s to represent the number n
l-calculus Functions + some basic
steps for manipulating functions
34
Lecture 2: Computability – TM and l-calculus
In TM, what is 1111?
In l-calculus: what is 3? In TM, what are the
basic steps?
In l-calculus, what are the basic steps?
3
λfx. f (f (f x)) Read/write/move tape
+ state change
Reduction, substitution, currying…
011110111110
Any Qs?
S0
State Table for addition:
[S0,0,S1,1 ] [ S0, 1, S0, >> ]
[ S1, 1, S1, << ] [ S1, 0, S2, >> ]
Note S0 is also known as the start state and S2, the halt state (i.e any state with no entries in the table)
56
1
8/25/21
Pure l-calculus
Formally, l-calculus consists of l-terms:
M, N are arbitrary l-terms What are these?
x y l-terms
(x (ly.(a b))) A list of 2 l-terms
lx.(y z) (lx. (ly. (x y))) Function definitions
(x y)
lx.x
((lx.x) y) or (lx.x) y Function application
Pure l-calculus in terms of LISP
l-calculus l-terms x y
A list of 2 l-terms
Function def
Function application
(x y) (x (ly.(a b))) lx.(y z)
LISP
LISP variables LISP lists (defun …)
(cons ‘a ‘(b c))
lx.x
(lx. (ly. (x y)))
((lx.x) y)
78
Pure l-calculus
Formally, l-calculus consists of l-terms:
M, N are arbitrary l-terms
A l function with 3 args So, what is this: λnfx.f (n f x) but what is the function?
A successor function
l-calculus SUCC := λnfx.f (n f x)
So, how does it work, say, compute succ 0?
Succ 0 = λnfx.f(n f x) (λfx. x)
Note that only ONE argument supplied, where does it go to?
0?
1 step: don’t need to
st λnfx.f(n f x) (λfx. x) So unlike PLs, you supply all the args
9 10
l-calculus SUCC := λnfx.f (n f x)
So, how does it work, say, compute succ 0? Succ 0 = λnfx.f(n f x) (λfx. x)
1st step:
It is a function with no args provided but what about inside this bracket?
λnfx.f(n f x) (λfx. x)
= λfx.f((λfx. x) f x) How do you interpret this?
1st step:
It is a function with no args provided but what about inside this bracket?
interpret this?
l-calculus SUCC := λnfx.f (n f x)
Succ 0 = λnfx.f(n f x) (λfx. x)
λnfx.f(n f x) (λfx. x)
= λfx.f((λfx. x) f x) How do you
((λfx. x) f x) is a function application with 2 args f & x. So, we can reduce it.
11 12
2
8/25/21
l-calculus
Succ 0 = λnfx.f(n f x) (λfx. x) Note that this does
not mean f goes into f. Rather, f goes into the 1st arg which happens to be an f
1st step:
λnfx.f(n f x) (λfx. x) = λfx.f((λfx. x) f x)
λfx.f((λx. x) x) λfx.f x = 1
((λfx. x) f x) is a function application with 2 args f & x. So, we can reduce it.
λfx.f((λfx. x) f x) λfx.f((λx. x) x)
So, which of the following languages would allow us to write more computable functions and hence is a more powerful language?
Java
C C++ Simula BCPL LISP Wai Basic
None because every computable function can be written using them. Technically, they are Turing equivalent.
13 14
So, which of the following languages would allow us to write more computable functions and hence is a more powerful language?
C++ Simula
Java C
C++ Simula BCPL LISP
But, which ones allow us to write better programs, solve problems faster, solve problems easier, etc.?
Or, for some of you, which ones allow us to get a job, to make more money, etc.?
Functional vs Imperative Style
Imperative languages: You manipulate the “values” stored in memory to produce the results you wanted.
Functional languages: You manipulate functions to produce the results you want.
Comments? Don’t you feel that way when you run the TM and the λ-calculus
15 16
Lecture 4: Grammar
Needed to help us write in that language!
But, not as complex as natural language, why?
Interpretation based on word meanings but PLs are based on ?
Interpretation could be ambiguous but PLs are not unless ?
An underlying machinery
Grammar is ill- defined. Ex?
Desiderata for the design of a PL
An unambiguous grammar
An effective implementation of it
An underlying machinery powerful enough to support it
17 18
3
8/25/21
Chomsky Classification
Type 0:
Type 1: Type 2: Type 3:
xày
xAy à x*y Aà*
Aàa AàaB
unrestricted context sensitive context free regular
Note that the above does not mean that all the rules of a given language must be of a single type!
An example of a regular grammar for
integeràdigit+ or not?
realàinteger exponent | decimal (exponent | ε ) decimalàdigit* (. digit | digit .) digit* exponentà(e | E) (+ | – | ε ) integer
digità0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
* Means 0 or more repetition and a + means 1 or more repetition.
defining numbers.
What do you look for to numberàinteger | real decide if this is regular
19 20
An example of Type 2: Grammar for Java:
declarations
What about grammar for LISP? Is it type 2?
Chomsky Classification
Type0: xày
Type1: xAyàx*y
Type2: Aà*
Type3: Aàa AàaB
What else can we say about this classification?
It is a hierarchy of types
What does this mean?
Which type is the most powerful?
21 22
Significance of Chomsky’s classification?
Allow us to define a grammar in a progressive manner
Allow us to look at what machinery is needed to support a grammar
Allow us to identify what kind of grammar is suitable for PLs
Machinery needed to support these grammars
Type 0: xày Type1: xAyàx*y Type 2: Aà*
Type3: Aàa AàaB
Turing Machines
Linear bounded automata
Not in syllabusJ Pushdown automata
We will learn more later and so not in this testJ Finite State Machines
23 24
4
8/25/21
Limitations of these grammars
Type 0: xày
Type1: xAyàx*y
Type 2: Aà*
Type3: Aàa AàaB
Support all computable functions Allow context to be recognised
Support recursion No recursion
PLs are defined using which type?
What do these sentences tell us about NL?
The cat the dog chased likes fish
He likes her and they like to play rugby
Natural language is recursive and context sensitive Is TM powerful enough to support natural language?
25 26
Lecture 5: Compilation – Issues raised
Program text converted to tokens/terminals of the language
What phase is this? Lexical analyser
What additional step is needed? Put name tokens in a symbol table
Why do we need to put name tokens in a symbol table?
Variable names, unlike other tokens such as “+”, “-”, cannot be processed immediately. They have run-time values.
So, how do we store them? Use a hash table
27 28
What problems do we face constructing a symbol table?
Need to handle collison; thereby creating a Name Table
Need to pre-hash reserved words (including names of pre-defined functions)
Need to keep a list of run-time properties of variables in a Pushdown List
“x” / “..” What are these run-time
P1 P2 flags P3
properties?
P1 – pointer to some runtime information about the name
P2 – pointer to the variable identity i.e. its actual name
P3 – pointer to the code of the procedure if any
29 30
5
8/25/21
Possible flags:
Declaration status: yes or not
“x”
Declaration type e.g. integer, real,.. Variable type: reserved or user-defined
Block level number
Offset value are these two?
Hmm..what
P1 P2
/ “..” flags P3
What is not stored in a symbol table?
Storage required (for variable value, array, etc.)
Why not?
Storage must be allocated separately during run-time; otherwise, can’t support recusion
31 32
In other words, we don’t have:
To do this: X := 5
P1 P2
“x”
flags
“x”
/ “..” value P3
/ “..”
P1P2 flags 5
P3
This is known as
static allocation
of storage as found in early languages (ex. Fortran 77).
Disadvantages?
P1 P2
“x”
flags
/ “..” value P3
No recursion! Why?
Because if you allocate value there, what happens when you call your function again?
33 34
From lexical analyser to syntax analyser
tokens program Symbol
table
What happens when LA passed a token “s.plus” to theSA? SAstartstocreateatree
What happens when LA passed a token “s.name” to the SA? SA creates the run-time of the
variable and continue to build a tree
Your Java
Lexical Analyser
Syntax Analyser
LISP Exercises:
Write a LISP function, sum-magic, which given a list of numbers will return the sum of the second and second last number.
Ø(sum-magic ‘(1 2 3 4 5)) à 6
Ø(sum-magic ‘(1 2)) à 0 Ø(sum-magic nil à 0
Pay attention to the examples!
35 36
6
8/25/21
LISP Exercises:
(defun sum-magic (L)
(cond
Ø(sum-magic ‘(1 2 3 4 5)) à 6 Ø(sum-magic ‘(1 2)) à 0 Ø(sum-magic nil à 0
Ø(sum-magic ‘(1 2 3 4 5)) à 6 Ø(sum-magic ‘(1 2)) à 0 Ø(sum-magic nil à 0
1st: set up the correct arg 2nd: think of the conditions
Add 2nd and 2nd last
< 4 elements returns zero Empty list returns zero
3rd: put the conditions in the function
(defun sum-magic (L) (cond ((null L) 0)
((< 4 elements) 0)
((add 2nd and 2nd last) 0)))
Add 2nd and 2nd last
< 4 elements returns zero Empty list returns zero
37 38
4th: write in proper LISP
(defun sum-magic (L) (cond ((null L) 0)
((< 4 elements) 0)
(t (add 2nd and 2nd last))))
That means the list must be of length > 4
That means we have to pick out 2nd element and 2nd last element and add them together
4th: write in proper LISP
(defun sum-magic (L) (cond ((null L) 0)
((< (length L) 4) 0) (t (+ (second L)
(second (reverse L))))))
That means the list must be of length > 4
pick out 2nd elementà use (second) and 2nd last elementàuse 2nd of the reverse list
39 40
LISP Exercises:
Write a LISP function, merge-list, which given L, a list of lists, will return a list that combines the first and the last list in L.
Ø(merge-list ‘((a b c) (d e f) (g h i)) à (a b c g h i)
Ø(merge-list ‘((1 2 3))) à (1 2 3) Ø(merge-list nil à nil
Again, think of the conditions:
Ø(merge-list ‘((a b c) (d e f) (g h i)) à (a b c g h i) Ø(merge-list ‘((1 2 3))) à (1 2 3)
Ø(merge-list nil à nil
Empty list returns nil
Single list – returns itself
Otherwise, combine first and last list
41 42
7
43 44
8/25/21
3rd: put the conditions in the function
(defun merge-list (L) (cond ((null L) nil)
((single list) list)
((combine 1st and last list)))
Empty list returns nil Single list – returns itself
Otherwise, combine first ad last list
4th: write in proper LISP
(defun merge-list (L) (cond ((null L) 0)
((single list) list)
((combine 1st and last list)))
Can use (null (cdr L))
1st list: (car L) Last list: (last L) Combine them: ?
4th: write in proper LISP
(defun merge-list (L) (cond ((null L) 0)
((null (cdr L)) (car L))
(t (cons (car L) (last L))))
Why cons?
Last always returns a list of the last element
Can use (null (cdr L))
1st list: (car L) Last list: (last L) Combine them: ?
45
8