PL01
7/13/21
1
1
What is this course about?
1
2
Your paper descriptor shows:
• Foundations of programming languages
• Principles of compilers and interpreters
• Runtimes and virtual machines
• Programming paradigms
COMP712: Programming Languages
Your paper descriptor shows:
• Foundations of programming languages
• Principles of compilers and interpreters
• Runtimes and virtual machines
• Programming paradigms
What make languages tick!
2
3
A programming language is a formal
computer language designed to
communicate instructions to a
machine, particularly a computer –
Wikipedia
Coded language used by
programmers to write instructions
that a computer can understand to
do what the programmer (or the
computer user) wants
A programming language is a formal
computer language designed to
communicate instructions to a
machine, particularly a computer –
Wikipedia
Coded language used by
programmers to write instructions
that a computer can understand to
do what the programmer (or the
computer user) wants
3
4
Examples:
Array in C#:
int[] X = new int[] {0, 1, 2, 3}
Array in Java:
int[] X = new int[] {0, 1, 2, 3}
int X[] = new int[] {0, 1, 2, 3}
Array in Snobol:
X = array(‘25’) Y = array(‘25, 3’)
4
5
If so, why do we have so many
different PLs? Why not
write in machine codes?
Because it is not
just about
telling the
computer what to
do!
5
6
What about finding a solution
that runs on a computer?
problem
Find a
solution
coding
These 2 processes
are not
independent, why not?
6
7/13/21
2
7
Simply, you
can’t just think
of any solution;
it has to be
“codable” on a
computer!
7
8
For example, in
the early PLs,
there was no
function and so
you Can’t write
recursive solution
8
9
Simply, you
can’t just think
of any solution;
it has to be
“runnable” on a
computer!
9
10
For example, in the
early days with
limited memories,
you Can’t write a
solution for
manipulating large
data
10
11
So, in designing a PL we
have to think about:
Efficiency
clarity
power
simplicity
:
11
12
A good PL should empower
you to find “good” solutions
to a problem.
At least, it should not hinder/
distract your thought process
unnecessarily.
12
7/13/21
3
13
A good
programmer, on
the other hand,
knows what the
PL is designed
for and how best
to use it.
13
14
So, it is not about:
problem
solution program
But rather:
problem
solution
+ PL
14
15
PL is a virtual
machine to a
programmer. Why?
problem
+ PL
solution Because your program
is designed using its
commands rather
than the commands in
a computer.
15
16
Examples:
Array in Java:
int[] X = new int[] {0, 1, 2, 3}
int X[] = new int[] {0, 1, 2, 3}
No machine understands the above
instructions
But they work! So, you could imagine
there exists a Java virtual machine that
understands them.
16
To a coder, a PL
is just a set of
instructions but
not to a real
programmer
problem
To a programmer,
a PL empowers
you with
different ways to
find a solution to
your problem.
problem
+ PL
solution
17
18
Studying PLs is about studying:
1. How PLs themselves work
2. How PLs support problem
solving
3. The trade-offs in PL design
18
7/13/21
4
19
So, that means (for us):
1. How PLs work Compiler
2. How PLs support
problem solving
LISP (& Prolog)
3. The tradeoffs in
PL design
Different PL
paradigms
(your project)
19
20
But why LISP?
1. Because it is unfamiliar to you
2. It is a beautiful language that
has influenced the design of
many modern PLs
3. You can use your favourite
language with which to compare
20
How the course will work
• 1 x 2hr lectures per week
• 1 x 2hr lab per week
• Directed learning – 102 hrs
• Lectures are essential – I interact with you and share
my experience
• One lecture is compulsory: WK7 mid-term test (15%)
21
21
22
1. Intro
2. TM & l-calculus, FP&LISP
3. LISP basic & Grammar
4. Grammar/Lexical Analyser (LA)
5. Lexical Analyser
6. LISP
7. Mid-term Exam + Q&A
8. Parsing
9. Prolog
10. Project Evaluation Week
11. Languages Comparison
12. Revision
Course
Outline
22
Tutorials
1. One stream(!) – Thurs 4-6pm WS221
23
2. Your tutor this year – Robert Le
Tutorial should not be just about doing
the exercises but it is also a time for
you ask us questions about the course!
23
Tutorial Format
• 15-20 mins closed book “exam” on previous
lecture
24
• 15-40 mins further exercises
• 40 mins to re-do the “exam” with your notes,
ask questions, do assignments, discussions, etc.
Robert will be in-charge and I will try to come in
the early part of the tutorial.
24
7/13/21
5
Assessments
1. 1 mid-semester test (15%, 25/8 week 7 – held
during lecture – Time: 1 hr+. Closed book. Aim:
To make sure you grasp the basic ideas
discussed so far.
25
3. 1 x 2hr final exam on all topics (50%). Closed
book.
2. One assignment (30% written + 5% oral =
35%). Due 15/9 no extension.
25
26
Write an essay comparing the differences in the
implementation of THREE different design concepts in
SIX different programming languages as per the
conditions below:
1. One of the programming languages must be LISP.
2. Provide references to your source
3. Each comparison must be done between two
programming languages; henceforth your essay
should have 3 sections, each comparison focuses on
how they differ in their implementation of the design
concept. Provide codes to illustrate, if possible.
26
27
4. Examples of design concepts include:
programming language paradigms (e.g.
functional vs OO), Security issues, garbage
collection, macros, high-level vs low-level
language design, encapsulation , concurrency,
evolution of languages (show how the language
has improved), etc.
27
28
5. Each section of your essay must consist of two
parts. Part A: a description of the differences
and why they differ, with coding examples if
possible. Part B: a detailed discussion of what
you have learned from researching the
differences and the design concept itself. Here
you may make references to other languages to
make a point, discuss the history/motivation of
the design concept itself, discuss the need and
usefulness of such a concept, etc. It is expected
that part B will be the larger section and the two
parts should be about ¾ of a page at most.
28
29
Marking Scheme
5 marks for each part which gives a total of 30 marks. Marking scheme
is as follows:
1. Part A – Mark is given for completeness, clarity and interestingness
which showed you have done a good (re)search.
2. Part B – Mark is given for interestingness which showed that you
have understood the topic.
3. Giving good references should help in convincing that you have
done the project well.
4. Hmm..where is the extra 5%? You will be interviewed for about 5
mins each – Mark is given for demonstrating to us (me and the TA)
that you understood what you have written (by answering a couple
of questions from us). Interviews are conducted during the lecture
on Week 10 and the tutorials of Weeks 10 and 11.
29
Resources
• AUTonline – lectures slides + tutorial exercises
• No prescribed course textbook
• Me – you can come and see me anytime in
WT410 or email me: wai. .nz (but
an appointment will make sure I am there)
• Discussion Board – No, I prefer to talk to you
in person!!
• Tutorials – Yes, I will be there for about 1 hr!
30
30
mailto:wai. .nz
7/13/21
6
Resources – Textbooks
• Bornat, Understanding and Writing Compilers: A
do-it- yourself guide. Internet Edition 2008 (you
can download this free) – for compilers
• Winston, Horn, LISP (3rd Edition) Pearon 1989 –
for LISP (if you get other books, make sure it is
about COMMON LISP.
• Scott, Programming Language Pragmatics (3rd
edition), Morgan Kaufmann, 2009 – for
background reading only.
31
31
About me & my teaching style
32
Always start on time (except today, I wait J )
Come and see me anytime – no need to
make an appointment but if you wish to
make one, feel free.
Email me if you wish – ask me a question,
make an appointment, invite me for coffee
J or whatever – I don’t bite!
32
About me & my teaching style
33
I like to ask you questions J I want to
encourage you to think about what I said
I make some of the slides available in the
BB before the lecture and the full slides
after.
Programming is not my first love; AI is! But
programming is my most important tool.
33
That means you have to:
34
Come on time and best not to miss a lecture
Prepare before coming to lecture
Interrupt me and ask questions. When
asked, try your best to answer – don’t
be shy!
Participate in tutorials – use your
tutorials creatively
34
000011 00001 00010 00011 00000 110000
What could this be?
35
It is a 32-bit instruction.
If the 1st 6 bits is for function code, what
do you have?
35
000011 00001 00010 00011 00000 110000
Could also be split into:
36
instructions
register1
register2
Memory address
Do all machines codes need to have an
address?
36
7/13/21
7
0000 Turn on kettle
0001 Turn off kettle
0010 Turn on heater
0011 Turn off heater
0100 repeat
No, and here is an example:
37
So, a machine code is truly a “language” we
use to “talk” to a machine!
Why do I put “language” in quote?
37
Why do some codes have addresses and some
don’t?
38
What codes can we have?
Some simple but interesting questions to
ponder:
Answering these questions amount to
designing a “language” for the machine!
38
39
In other words, not just to control a kettle but
one that can do different things!
The codes are tied to what the machine can
do which leads to an interesting question: can
we have a general purpose machine?
0000 Turn on kettle
0001 Turn off kettle
0010 Turn on heater
0011 Turn off heater
0100 repeat
39
40
Yes but we need a way to combine different
instructions to perform different tasks
Program = instructions + memory
Instructions = actions + controls
So, can we have a general purpose machine?
40
41
A simple program
0011: 0010 0001
0101 0011
What does the above program do?
0011: INC 0001
JMP 0011
So, you don’t want to write in machine code,
do you?
What are
these?
Mnemonic
codes
41
42
assembler
Machine code Assembly code
disassembler
You need an assembler:
A simple program
0010
0101
INC
JMP
42
7/13/21
8
43
While writing in assembly language helps
you to remember the machine codes easily,
you are still thinking in terms of how the
machine works! Why?
Because you can’t do abstract computations:
(+ 1 2) or x = 1 + 2;
Instead you do: MOV A, 1000
MOV B, 1001
Add A, B
43
44
So, to solve a problem you need to think
explicitly where you store the values in
memory(!) and where you want to retrieve
them before thinking about to do with them.
MOV A, 1000
MOV B, 1001
Add A, B
Locations where
you put values 1
& 2
registers
44
45
Program abstraction
Actions
Control
Memory
Abstraction is the Key!
assignment, procedures, etc.
while-loop, for-loop, etc.
array, record, etc.
A key concern in language design is thus
finding ways to facilitate our ability to solve
problems in an abstract manner
45
46
Abstraction leads to different ways of solving
a problem. For example:
The greatest common divisor (GCD), also
called the greatest common factor, of two
numbers is the largest number that divides
them both. For instance, the greatest
common factor of 20 and 15 is 5, since 5
divides both 20 and 15 and no larger number
has this property. Write a function to do so.
46
47
Abstraction leads to different ways of solving
a problem
Int gcd(int a, int b) {
while (a != b) {
if (a > b) a = a – b;
else b = b –a;
}
return a;
}
(defun gcd(a b)
(cond ((equal a b) a)
((a > b) (gcd (- a b) b)
(t (gcd b a))))
gcd(A, B, C) :- A=B, C=A
gcd (A, B, C) :- A>B, D is A-B, gcd(D, B, C)
gcd(A, B, C) :- B>A, gcd(B, A, C)
What do you see above?
47
48
What a good programmer sees is not just how the
code is written but how the problem is solved
Int gcd(int a, int b) {
while (a != b) {
if (a > b) a = a – b;
else b = b –a;
}
return a;
}
(defun gcd(a b)
(cond ((equal a b) a)
((a > b) (gcd (- a b) b)
(t (gcd b a))))
gcd(A, B, C) :- A=B, C=A
gcd (A, B, C) :- A>B, D is A-B, gcd(D, B, C)
gcd(A, B, C) :- B>A, gcd(B, A, C)
While
loop recursion
logic
48
7/13/21
9
49
Compiler
Machine code
De-compiler
Programming
language
A program that converts your high-level
language to machine code is a compiler
49
50
1. No direct correspondence to the machine
code
That means you need to be smart to generate
efficient code! [e.g. FORTRAN is a very efficient
compiler because lots of people work on it to
make it so]
Is it obvious to you that a compiler needs to
be more sophisticated than an assembler?
I hope so but, why?
50
51
Hence, we could have several versions of the
same language (e.g. dialects in LISP)
2. There could be different ways to do the
same thing and this could lead to different
interpretations and/or unexpected side-
effects!
Is it obvious to you that a compiler is more
sophisticated than an assembler? But why?
51
52
3. Could the machine support your language?
For example, could your language be
implemented for an 8-bit machine [e.g. in
the good old days, LISP finds it hard].
This is particularly the case in the early days
when machines have limited memory and the
design of language starts to incorporate many
powerful features (e.g Ada).
Is it obvious to you that a compiler is more
sophisticated than an assembler? But why?
52
53
Compiler
Machine code
De-compiler
Programming
language
Does a compiler always have to generate the
code for execution?
No, but why not?
Because it is already a sophisticated
program – how about interpreting
the incoming program itself?
53
54
Initial idea is to compile the source program
into the machine object code and then run
the code:
Compiler vs Interpreter
54
7/13/21
10
55
However, the compiler can generate an
interpretation of the program itself given that
it itself is a program. Such a compiler is called
an interpreter:
Confused?
55
56
Here is an example:
Consider a simple language called MATHs
that allows you to write simple arithmetic
statements:
1 + 6 – 2;
2 * 5;
3 + 2 * 5;
5
10
25
56
57
A simple compiled program for MATHs:
1 + 6 – 2;
2 * 5;
3 + 2 * 5;
STO 1, 1000
STO 6, 1001
STO 2, 1010
MOV A, 1000
ADD A, 1001
SUB A, 1010
PRT A
:
57
58
But, what does compiler need to do in order
to generate the code?
1. It needs to read in each line of
mathematical expression.
2. It needs to recognise the numbers
3. It needs to recognise the operators
But, if compiler (a program in itself) recognises
a number follows by a “+” and a number, why
can’t it just add them!
58
59
Henceforth:
1 + 6 – 2
Aha: this is 7
And: this is 5
Read
1
Read
6
Read
2
Read
+
Read
–
An
Interpreter
59
60
import java.util.Scanner;
class AddNumbers
{
public static void main(String args[])
{
int x, y, z;
System.out.println(“Enter your program”);
Scanner in = new Scanner(System.in);
x = in.nextInt();
y = in.nextInt();
z = x + y;
System.out.println(“Sum of the integers =
” + z);
}
}
Here is an
interpreter!
Interpreting
here
60
7/13/21
11
61
1. When do we write a compiler versus an
interpreter?
2. Can we have a mixture of both and why?
On Compiler Design
3. Since a compiler is a program that can set
up the execution of other programs, what
else could it provide?
Linker? Debugger? A programming
environment?
61
62
As you know, there are many programming
languages but why?
1. Designed for different use.
2. Designed for different philosophy.
Example – Pascal for teaching; Cobol for banking
Example – Prolog as a logical programming;
Lisp for symbolic reasoning
62
63
3. Designed for universal use.
Example – Ada is meant to emerge out of the
many languages being used by the US
Department of Defense (DoD)
Interestingly, in Wikipedi, it was mentioned
that with the development of Ada, there will
be two languages left, Ada & ?
As you know, there are many programming
languages but why?
63
Programming Languages
[what this course is about]
64
Understanding how a compiler works
Understanding the issues involved in
designing a programming language
While these are interesting issues, why do we
need to know? Why can’t we just learn how to
use a particular language?
64
Programming Languages
[what this course is not about]
65
Learning many different programming
languages
Learning how to write programs in different
languages
Nonetheless, you will learn the use of a new
language and use it to discuss design issues.
65
66
No
Textbook!How am I going to study?
Help!
66
7/13/21
12
67
There are
plenty of books
67
But why didn’t I choose one?
68
These books make wrong assumptions
about your background
My views of programming languages are
not the same
It is time that you should not read from a
single book and just follow what it says.
68
69
What are the key
concepts/ideas from
the lecture?
How to study in this course
Get some books and
read more about them.
Identify what you do
not understand.
Seek help in the
tutorials or see Albert
69
70
Go to lectures and
tutorials!
How to study in this course
Ask Qs in lectures and
in tutorials
Answer Qs in tutorials
and assignments
Pass with flying
colours!
70
Topics for the next lecture
71
Functional Languages and some LISP
Abstraction, Turing Machines,
Computable functions and l-
calculus
71