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

1st semester 2019

Prabhas Chongstitvatana

official course description

Principal lecturer: Prabhas

This course is divided into three equal parts.

1) Programming Language concepts, Prabhas and Vishnu
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%

Theory of programming language

Evolution of programming language
Names, scope and binding
Control flow
Data types
Control abstraction
Data abstraction and object

additional:

intro to assembly language

Functional Programming

Backus Turing award lecture 1978

Example: Matrix muliplication in FP

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. You will be studying actual compilers and modify them.

old lecture 2016 2017 2018

Announcement

16 Sept 2019 --- Quiz 1 will be on Wed 18 Sept, 8:30am. Topic covers all lectures except Object and Assembly

. . .

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

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
     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
        a recursive descent parser for a simple language
        a parser with building parse tree
        LL1 parser of grammar from lecture parsing page 25 (LL1-parser.zip) (slide)
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 summary of compiler part

Assessment for this part

one project    10%
quiz              10%
total               20%

Classwork

. . .

Homework

16 Sept 2019 Functional programming:

1) Basic: Evaluate the function MM with this argument <<1,2,3>,<4,5,6>,<7,8,9>>
(that is, write its execution as algebra on the paper).
2) Advance: Implement MM with your favourite language such as Python (using functional). There are many other functional languages suitable to do it, such as SCHEME, ML, Haskell etc.
3) Write AVERAGE that takes input sequence and compute the arithmetic mean.
AVERAGE:<1,2,3> = 6 (You can assume integer arithmetic)

. . .

Project

. . .

Reference Text

-- NEW ! Jaruloj Chongstitvatana, Programming Languages Principles and Processing, (local copy) 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

A chart of genealogy of programming languages (pdf) (You need to zoom to 100% to see it)
Your friend comes to ask me about Functional programming and why it does not have assignment. A simple answer is that Functional Programming relies on "referential transparency" hence it does not have side-effect. Unlike "imperative" (or we can call it "procedural") programming, functional programming does not even have to use "variable". Can you imagine that? For those curious mind, read this foundation paper on Functional Programming. Backus Turing award lecture 1978

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 rz36-3.zip

lexical analyser (lex-35-3.zip, extract from rz35-3 package)

Rz compiler on the web (by Kamoluk Suksen)

New example of a recursive descent parser for a simple assembly language asm-summer-2.zip
LL1 parser from lecture parsing page 25 LL1-parser.zip

[ Zero Assembler source, example and executable (including som v2 vm) ( zas.zip ) ]

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)\
Retro Basic lister (lister.zip) and interpreter (interp.zip)

How to use the compiler

Use rz36 to compile and run your programs. Here is what a session looks like. Go to rz36/test directory (that you unzip the package to). There are three executable files: rz36.exe, as21.exe, sim21.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:\rz36\test>rz36 fac.txt

      fac

      main

      (fun main (print (call fac 6 )))

      (fun fac (else (== #1 0 )(return 1 )(return (* #1 (call fac (- #1 1 ))))))

      

      

          ...

You will get the assembly file as an output file. Then, use as21.exe to "assemble" (change assembly file into object code file). You can "run" it under s2 simulator (execute machine code) s21.exe.

D:\rz36\test>sim21 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 17 Nov 2019