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 and Homework of Section 3

Classwork and Homework of Section 2

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

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