# CS代考 8/25/21 – cscodehelp代写

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