7/13/21
COMP712 Programming Languages Lecture 1: Introduction Albert Yeap WT410 AUT University 2021
What is this course about?
1
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
12
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
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
34
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
What about finding a solution that runs on a computer?
problem
Find a solution
coding
These 2 processes are not independent, why not?
6
56
1
7/13/21
Simply, you can’t just think of any solution; it has to be “codable” on a computer!
7
For example, in the early PLs, there was no function and so you Can’t write recursive solution
8
78
9 10
Simply, you can’t just think of any solution; it has to be “runnable” on a computer!
9
For example, in the early days with limited memories, you Can’t write a solution for manipulating large data
10
So, in designing a PL we have to think about:
Efficiency clarity power simplicity :
11
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
11 12
2
7/13/21
A good programmer, on the other hand, knows what the PL is designed for and how best to use it.
13
So, it is not about: problem
solution
program
+ PL
solution
But rather:
problem
14
13 14
problem
+ PL
solution
PL is a virtual machine to a programmer. Why?
Because your program is designed using its commands rather than the commands in a computer.
15
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
15 16
problem
To a coder, a PL is just a set of instructions but not to a real programmer
problem
+ PL
solution
To a programmer, a PL empowers you with different ways to find a solution to your problem.
Studying PLs is about studying:
1. How PLs themselves work
2. How PLs support problem solving
3. The trade-offs in PL design
18
17 18
3
7/13/21
So, that means (for us):
1. How PLs work
2. How PLs support problem solving
3. The tradeoffs in PL design
Compiler
LISP (& Prolog)
Different PL
paradigms (your project)
19
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
19 20
How the course will work
• 1x2hrlecturesperweek
• 1x2hrlabperweek
• Directedlearning–102hrs
• Lecturesareessential–Iinteractwithyouandshare my experience
• Onelectureiscompulsory:WK7mid-termtest(15%) 21
Course Outline
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
22
21 22
Tutorials
1. Onestream(!)–Thurs4-6pmWS221
2. Yourtutorthisyear–RobertLe
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
• 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
23 24
4
7/13/21
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.
2. One assignment (30% written + 5% oral = 35%). Due 15/9 no extension.
3. 1 x 2hr final exam on all topics (50%). Closed book.
25
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
25 26
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
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 3⁄4 of a page at most.
28
27 28
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: (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
29 30
5
7/13/21
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), , 2009 – for background reading only.
31
About me & my teaching style
Always start on time (except today, I waitJ)
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
31 32
About me & my teaching style
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:
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
33 34
What could this be?
000011 00001 00010 00011 00000 110000
It is a 32-bit instruction.
If the 1st 6 bits is for function code, what do you have?
35
Could also be split into:
000011 00001 00010 00011 00000 110000 instructions
register1register2
Memory address
Do all machines codes need to have an address?
36
35 36
6
7/13/21
No, and here is an example:
0000 Turn on kettle 0001 Turn off kettle 0010 Turn on heater 0011 Turn off heater 0100 repeat
So, a machine code is truly a “language” we use to “talk” to a machine!
Why do I put “language” in quote?
37
Some simple but interesting questions to ponder:
Why do some codes have addresses and some don’t?
What codes can we have?
Answering these questions amount to designing a “language” for the machine!
38
37 38
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
In other words, not just to control a kettle but one that can do different things!
39
So, can we have a general purpose machine? Yes but we need a way to combine different
40
instructions to perform different tasks
Program = instructions + memory Instructions = actions + controls
39 40
A simple program
0011: 0010 0001 0101 0011
What are these?
What does the above program do? Mnemonic
0011: INC 0001 JMP 0011
So, you don’t want to write in machine code, do you?
codes
41
A simple program
You need an assembler:
disassembler
Assembly code
INC assembler JMP
Machine code
0010 0101
42
41 42
7
7/13/21
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
MOV A, 1000 Locations where MOV B, 1001 you put values 1
&2
registers
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.
44
Add A,B
43 44
Program Actions Control Memory
abstraction
assignment, procedures, etc. while-loop, for-loop, etc.
array, record, etc.
Abstraction is the Key!
A key concern in language design is thus
finding ways to facilitate our ability to solve problems in an abstract manner
45
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
45 46
Abstraction leads to different ways of solving a problem
Int gcd(int a, int b) { while (a != b) {
(defun gcd(a b)
(cond ((equal a b) a)
((a > b) (gcd (- a b) b) (t (gcd b a))))
}
return 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)
if (a > b) a = a – b; else b = b –a;
What do you see above?
47
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; While else b = b –a;
loop }return a;
(defun gcd(a b)
(cond ((equal a b) a)
((a > b) (gcd (- a b) b) (t (gcd b a))))
recursion
} gcd(A, B, C) :- A=B, C=A
logic gcd(A, B, C) :- A>B, D is A-B, gcd(D, B, C)
gcd(A, B, C) :- B>A, gcd(B, A, C)
48
47 48
8
7/13/21
A program that converts your high-level language to machine code is a compiler
De-compiler
Programming language
Machine code
Compiler
49
Is it obvious to you that a compiler needs to be more sophisticated than an assembler?
I hope so but, why?
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]
50
49 50
Is it obvious to you that a compiler is more sophisticated than an assembler? But why?
2. There could be different ways to do the same thing and this could lead to different interpretations and/or unexpected side- effects!
Hence, we could have several versions of the same language (e.g. dialects in LISP)
51
Is it obvious to you that a compiler is more sophisticated than an assembler? But why?
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).
52
51 52
53 54
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
Machine code Compiler
the incoming program itself?
53
Compiler vs Interpreter
Initial idea is to compile the source program into the machine object code and then run the code:
54
9
7/13/21
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
Here is an example:
Consider a simple language called MATHs that allows you to write simple arithmetic statements:
5 10 25
1 + 6 – 2; 2 * 5;
3 + 2 * 5;
56
55 56
A simple compiled program for MATHs:
1+6-2; STO 1,1000 2*5; STO 6,1001
3 + 2 * 5;
STO 2, 1010 MOV A, 1000 ADD A, 1001 SUB A, 1010 PRT A
:
57
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
57 58
Henceforth:
1+6-2
1 Read 6 Read 2
–
Aha: this is 7
And: this is 5
Read Read Read An
+
Interpreter
59
Here is an interpreter!
Interpreting here
} }
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);
60
59 60
10
7/13/21
On Compiler Design
1. When do we write a compiler versus an interpreter?
2. Can we have a mixture of both and why?
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
As you know, there are many programming languages but why?
1. Designed for different use.
Example – Pascal for teaching; Cobol for banking
2. Designed for different philosophy.
Example – Prolog as a logical programming; Lisp for symbolic reasoning
62
61 62
As you know, there are many programming languages but why?
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 & ?
63
Programming Languages [what this course is about]
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
63 64
Programming Languages [what this course is not about]
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
Help!
66
65 66
11
No
Textbook!
How am I going to study?
7/13/21
There are plenty of books
67
But why didn’t I choose one?
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
67 68
69 70
How to study in this course
What are the key concepts/ideas from the lecture?
Get some books and read more about them.
Identify what you do not understand.
Seek help in the tutorials or see Albert
69
How to study in this course
Go to lectures and tutorials!
Ask Qs in lectures and in tutorials
Answer Qs in tutorials and assignments
Pass with flying colours!
70
Topics for the next lecture
Abstraction, Turing Machines, Computable functions and l- calculus
Functional Languages and some LISP
71
71
12