2110316  Programming Languages Principles 3(3-0-6)

1st semester  2017

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 computer 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 machines 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%

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 I choose to design a toy language and implement its compiler. There are two implementation, in C and in Javascript. You will be studying actual compilers and modify them.

old lecture  2014  2015   2016

Announcement

16 Nov 2017  --  quiz in on Thursday 23 Nov 2017, 8:30am.  open book

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

Lecture sessions

Introduction to the course
1  structure of a compiler
       Intro to Compiler (ppt)  Supplement: Cross 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)  
--------------------------
3  grammar             
         Recursive programming with List    extra exercises    new lecture
         Context Free Grammar  (ppt)   Example of writing a grammar to specify a language
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   Example of writing  a recursive descent parser for a simple language
                           Example of a parser with building parse tree      
6  code generator        Code Generation     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
---------------------------
7  actual code generator  How to do code generation
    project announcement

Assessment for this part

one project       5%         
exam              15%   
total               20%

Classwork

  . . .

Homework

1.  Learn how to write in Rz by reading  Quick Start Rz.
2.  Download and compiler the compiler used in this class (rz35-3.zip).  Use whatever compiler for C that you are familiar with and compile it. Try it out to compile some simple program.   For recommended free C compiler, see Tools section below.
3.  Compile and try this lexical analyser  (lex-rz35-3.zip), it is a part of rz35-3.
4.  Do two homeworks in new lecture

Project

for Rotation 3  (5 points)

A language that "verbalise" programming.  Imagine how to help a blind person to write a computer program.  We can use speech recognition to "transcribe" sound to text.  However it is cumbersome to just spell out text of our conventional programing language.  Try to read this "hello world" aloud.

#include <stdio.h>

int main(void){
  printf("hello world\n");
  return 0;
}


Let us improve the "verbalisation" a little bit.  We can use "command" then follow by "parameters".  When the number of parameters is variable, we can use the word "stop" to delimit them. We can also use that to say the end of the code block.  Let us use this example:

square(x){
  return x * x;
}


We can verbalise it like this:

function square parameter x stop block return expression x mul x stop

Wow, this will be super good!

Now, back to your project,  use this idea to design your small language (you can use the above example, it is good enough to be used to write a simple program with no data type).  Give examples of your program, both input "speech" and output (C like).  Write the grammar for your language.  Write a parser in pseudo code (no need to generate output), a pure parser that parses proper input is sufficient.

What you have to submit:
1)  Your design of the language, examples of the language
2)  Grammar of your language
3)  Parser (in pseudo code) for your language

Due date

All the above in paper, put the report in "inbox" in front of my office (room 13 floor 18, Eng building 4) before 4pm 15 Dec 2017.

Bonus

You don't have to write an executable parser (such as writing it in C).  But, if you do write the "executable" parser, I will give an extra bonus (5 points) to be add to your final exam. score (however, the maximum of my part is still 20% now and 13% final).  If you did submit a real parser please email your project to me (I would like to give it a try) at   prabhas.c@chula.ac.th  with the subject line clearly state:  prog lang prin project.  Remember to include your name and id in your email so that I can give the credit correctly.

Reference Text

-- NEW ! Jaruloj Chongstitvatana, Programming Languages, Dept. of Math and CS, Chulalongkorn, 2017. (main 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 main text is Jaruloj.  It covers larger topics than required in this class.  Our presentation follows this textbook.  Aho,Sethi, Ullman is the standard textbook 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.   Louden is much easier to read.   The latest edition is 1997, you can find it in Amazon.

Extra reading

Tools

Recommended free C compiler for Windows lcc-win32 . (for Windows 7, 8, 8.1 and 10).  Please also download and install "User Manual". You need it to look up the library function of this C.  (for OS X you need xcode, also free). 

See my Rz language homepage
the compiler  package with code generator for s-code  rz35.zip  rz35-3.zip (use hash)
lexical analyser  (lex-35-3.zip,   extract from rz35-3 package)
Zero Assembler   source, example and executable (including som v2 vm) ( zas.zip )   
Rz compiler on the web  (by Kamoluk Suksen)
To practice recursive programming in the lecture, you need this library  ailib.zip  (in C).
Example of building parse tree   ex-parse-tree-2.zip  (clean up)

How to use the compiler

Use rz35  to compile and run your programs.   Here is what a session looks like.  Go to rz35/test directory  (that you unzip the package to).  There are two executable files:   rz35.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:\rz35\test>rz35 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:\rz35\test>somv2x fac.obj
720


That's it.  Enjoy!

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  21 Nov 2017
Statcounter