2110316 Programming Languages
Principles 3(3-0-6)
1st semester 2012
Prabhas Chongstitvatana
official course description
Principal lecturer: Twittee. This course is divided into three equal
parts. Three parts are taught by three different lecturers.
1) Programming Language concepts, Twittee
2) Non-imperative programming language, Vishnu
3) Language and implementation, Prabhas
The goal of this course is to make you understand the languages you use. To
make you appreciate diversity of ideas in programming and prepare you for
new programming methods and paradigms. Theoretical foundations will be
presented. You will know properties of language, not just syntax. Moreover,
you will recognize the cost of presenting an abstract view of machine and
understand trade-offs in programming language design.
Each part will be taught separately and independently. It is logical that
the assessment will also be arranged according to this structure. There is
no midterm exam (besides whatever assess by the lecturer at that time) and
the final exam will contain all materials taught in the course.
Assessment
each part 20% by 3 = 60%
final
exam
40%
the lecture schedule:
section 1: T, V, P
section 2: V, P, T
section 3: P, T, V
Language and implementation
This part concerns a compiler for a programming language. There are two
aspects of learning this part: theory and practice. The theory will be
given in the lectures. The practice is carried on as homework and
classwork. To teach effectively and to enrich your C programming skill, I
choose to design a toy language and implement its compiler in C. You will be
studying an actual compiler and modify it.
old lecture 2009 2010
2011
Announcement
7 June 2012 Add Quick
Start Rz to Rz homepage
5 July 2012 The last day of hand-in all works is 13
July.
All inquiries about your score (for Section 3) should be raised before the
end of July.
12 July 2012 The class on Tues 17 is cancelled (I will be in
Japan for a meeting of the international organizing committee of
ITC-CSCC2012).
The class meets again on 24 July.
9 Aug 2012 A quiz will be issued on Tuesday 14 Aug,
9:30am. The duration is 30 min. We will have lecture
afterward.
14 Sept 2012 Section 1 -- The project is announced. The
deadline for hand-in is 4pm, on 5 October 2012 at the box in front of my
office.
. . .
Study Plan
plan for 4 weeks, with one week to spare
each week has 2 sessions of 1 1/2 hrs. each.
a homework will be handed out each week.
one project will be issued on week 3.
workload
one small project
one in-class exam
weekly homework, running the code
Lecture sessions
1 structure of a compiler Overview
of the course (from Stanford slide) Compiler (ppt)
High Level Language to Low Level Language
to Processor architecture
Demonstrate the actual compiler of this course RZ.
2 lexical analyser Scanner
(ppt)
automaton
--------------------------
3
grammar
Context Free Grammar (ppt)
4 parsing
Parsing (ppt)
top-down parsing How to compute First
and Follow set (by Prof. Kamin at UIUC)
LL parser at Wiki
----------------------------
5 actual parser
project announcement
6 code generator Code
Generation (updated)
Som v2.0 virtual machine S-code
recursive evaluator here is the source
code in C for an interpreter of Rz parse tree
eval3.c
---------------------------
8 actual code generator How to do code
generation Zero Assember
exam
-----------------
9-10 spare additional topics Exascale
computing Look at the reference section at the bottom of the
page.
submit project
Assessment for this part
homework 5%
one project
5%
exam
10%
total
20%
Classwork
Section 1
1. Write a recursive program to fine a maximum value of all elements in an
array of integer.
2. Write a program to test whether the input is in the given list. The list
is a linked-list. A linked-list is implemented as a two-cell integers.
The first cell contains the information, an integer (greater than
zero). The second cell contains an index to the next two-cell. The
end-of-list is represented by the index 0 in the next-cell. Once you get it
write, change this program into a recursive version. Write it in Rz.
3. Write CFG to contain these sentences:
appl sue samsun, samsun sue appl, goog sue appl, appl win samsun, samsun
pay apple, samsun pay appl one-billion, appl pay samsun three-thousand,
goog buy moto, moto has patent, appl use patent to sue, goog use patent to
sue.
4. Write in som v2 assembly language the following statements:
4.1 a = 11 + 22;
4.2 if ( a != 0 ) b = 1;
else b = 2;
Homework
Section 1
1. Learn how to write in Rz by reading Quick
Start Rz.
2. Familiarize with the compiler tool. Use rz33-1.zip
to compile and run your programs in the classwork1.
Here is what a session looks like:
Go to rz33/test directory (that you unzip the
package to). There are two executable files:
rz33.exe and somv2x.exe
Try to compile "fac.txt". It is shown here:
// factorial
fac(n){
if( n == 0 ) return 1;
else return n * fac(n-1);
}
main(){
print(fac(6));
}
Here is the command line and the output at the screen:
D:\prabhas\bag\rz\rz33\test>rz33 fac.txt
fac
main
(fun main (print (call fac 6 )))
(fun fac (else (== #1 0 )(return 1
)(return (* #1 (call fac (- #1 1 ))))))
:main
fun.1
lit.6
call.fac
sys.1
ret.1
:fac
fun.1
get.1
lit.0
. . .
You will get the file "fac.obj" as an output
file. It is an object file that is executable under Som VM (a kind of
virtual machine similar to JVM). You can "run" it under somv2x.
D:\prabhas\bag\rz\rz33\test>somv2x fac.obj
720
That's it. Enjoy!
2. Download rz33-1 and try to compile the source. Use the
executable rz33.exe and somv2x.exe to compile and run your
program. Then modify the scanner so that it can cope with "case
insenstive" input. It is easy to do that only one or two lines
of code needed to be inserted into the scanner. Your only problem is
to locate where to insert it. Hand is a few lines of explanation how
you did it.
Project
Section 1
Design an object-oriented extension of Rz language. The report
contains:
1) The design of the language. A description of the
language. The motivation of your design.
2) Its Grammar (just the relevant part, not the whole Rz
language) in BNF or Railroad diagram
3) Give good examples of the use. (some programs in your
language)
The length of the report is about 4 pages. I am interested in the
"quality" of the report not the "quantity". You should try to explain
your idea in your own word. Define a language that is not trivial or is not
too big. Its grammar should be less than one page. Create interesting
examples. Write a good grammar. This is not a language
implementation issue. We concentrate on "design". The deadline for
hand-in is 4pm, on 5 October 2012 at the box in front of my office.
Reference Text
-- Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools.
Addison-Wesley, latest edition.
-- Louden, K.C., Compiler Construction: Principles and Practice. PWS
Publishing Co., 1997.
The first one is the standard text book on compiler. It has been used in
more than 100 universities in North America. It is a bit difficult to
read as it contains a lot of theory. The second one (Louden) is
much easier to read. I will update some chapter from my textbook from
time to time as necessary.
Extra reading
- A chart of genealogy of programming languages
(pdf) (You need to zoom to 100% to see it)
- Programming Recursion (to
familiar yourself with recursive programming)
- My
other programming language and its virtual machine: Som
- John Backus,
the father of FORTRAN compiler. He invented Functional
Programming. I have a discussion here.
(include the link to the original paper) vice1977 ACM Turing Award
lecture, John Backus, "Can Programming Be Liberated from the von Neumann
Style? A Functional Style and Its Algebra of Programs", Communication of
the ACM, vol.21, no.8, August 1978, pp.613-641.
- Here is the "interpreter" for Rz (parse tree). You can
incorporate in into rz33 package. It will "run" the parse tree
(but will fail at "return" in some
circumstances).
eval3.c
- I mentioned in the lecture of the crucial point of a start-up company.
This interview is an excellent article that tell me what a university
and undergrad education is. It is from our revere writer of the text
"computer architecture" that most of you have to endure :-) Enjoy!
http://tech.fortune.cnn.com/2012/06/20/stanford/
- I mentioned "skiplist" as an advanced data structure that use
"randomness" to improve the efficiency. Here is the reference: Pugh,
William (June 1990). "Skip lists: a probabilistic alternative to
balanced trees". Communications of the ACM 33 (6): 668–676.doi:10.1145/78973.78977.
You can also find the wiki here http://en.wikipedia.org/wiki/Skip_list
- For an example of the "most concise" input language, try APL invented
by Kenneth Iverson. Here is some reading at wiki : http://en.wikipedia.org/wiki/APL_(programming_language)
There are several short examples of the programs at near the end of the
article.
- Exascale computing: See my teaching page http://www.cp.eng.chula.ac.th/faculty/pjw/teaching/ads/ads2011/ads2011-index.htm
Look up the reference section at the bottom of the page
Tools
See
my Rz language homepage
the compiler package with code generator for s-code
rz33-1.zip
Zero Assembler: source, example and executable
(including som v2 vm) source: zas.c
Prabhas Chongstitvatana
contact address: prabhas at chula dot ac dot
th
office room 18-13 Engineering Building 4, floor 18.
tel 02-2186982
research lab: Intelligent Systems, floor 20.
Last update 18 Sept 2012