If you want to talk to me at other time, please make an appointment.
(reference only) R.W. Sebesta, Concepts of Programming Languages, 4th ed., Addison-Wesley, 1999.
(reference only) R. Stansifer, The Study of Programming Languages, 1995, Prentice-Hall.
(reference only) D.P. Friedman, M. Wand, and C.T. Haynes, Essentials of Programming Languages, 1992, MIT Press.
(reference only) R. Bird and P. Wadler, Introduction to Functional Programming, 1988, Prentice-Hall.
(reference only) W.F. Clocksin and C.S. Mellish, Programming in Prolog, 1981, Springer-Verlag.
(reference only) J.W. Lloyd, Foundations of Logic Programming, 1984, Springer-Verlag.
(reference only) D. Gries, The Science of Programming, 1981, Springer-Verlag.
(reference only) Models of Programming Languages and Computation, ACM Computing Surveys, 28(2), June 1996, whole issue. Check the table of contents.
(reference only) David H. D. Warren, Logic Programming and Compiler Writing, Software Practice and Experience, Vol. 10, pp. 97-125, 1980.
This course is an introduction to programming languages. Programming languages are a basic tool in computer science. We hope that the students can establish a firm background in languages and programming for further study.
We will study various programming paradigms and associated language constructs. Imperative languages will be our starting point. We will study types, variables, expressions, statements, control structures, subprograms, and modules. The principles of data encapsulation and inheritance will also be covered. After imperative languages, we will study functional languages and logic languages. Since parallel machines are becoming more and more practical and important, we will briefly study concurrent programming languages. A brief introduction to syntax and semantics will also be provided.
IT IS RECOMMENDED THAT YOU USE CHINESE TO ANSWER QUESTIONS IN THE EXAMS. YOU MAY ALSO USE ENGLISH IF NECESSARY. DO NOT USE ANY OTHER LANGUAGES.
Midterm: November 8, Tuesday, 10-12 am, 2005. Chapters 1 through 6, close book.
Final: January 10, Tuesday, 10-12 am, 2006. Chapters 7-12, close book.
These programming projects are all small projects. You need to do them all by yourself (not yourselves). You may discuss the projects with friends but never look at others' code. And never let others look at your programs.
The emphasis in these projects is to express your solutions as clearly as possible. Never worry about the amount of running time nor the amount of memory space required. A clear solution is better than a fast or small one in this introductory course.
ML, Scheme, and Prolog are available on the course page. See below.
void swap(x, y)
int *x, *y;
{ int z;
z = *x;
*x = *y;
*y = z;
}
The swap procedure exchanges the values stored in its two arguments.
Can you write another procedure that does the same thing but does not
make use of pointers and addresses? Why or why not?
call by value
call by reference
call by name
Find five programs so that (1) in the first program, the results
based on the three methods are identical; (2) in the second program,
the results based on the first two methods are identical but are
different fromt that based on the third method; (3) in the
third prorgram, the result based on the first and third methods are
identical but are different from that based on the second method; (4)
in the fourth program, the results based on the last two
methods are identical but are different from that based on the first
method; (5) in the fifth program, the results based on the three
methods are different.
Consider a game of evolution. A lifeform is represented as a sequence of genes. There are four kinds of genes: alpha, beta, gamma, and delta. Initially, there are only two kinds of lifeforms, called M = [alpha], and F = [beta], respectively. To generate new lifeforms, a lifeform may undergo a mutation process or two lifeforms may fuse or mate. Sometimes, lifeforms will compete for survival.
When a lifeform mutates, its odd-numbered genes are converted as follows: an alpha gene is converted to a beta gene, a beta gene is converted to a gamma gene, a gamma gene is converted to a delta gene and a delta gene to an alpha gene. For instance, the result of mutating [gamma, alpha, beta, alpha, delta] is [delta, alpha, gamma, alpha, alpha]. The length of the gene chain of the resultant lifeform is always the same as that of the original lifeform.
Two lifeforms with equal-length gene chains may be fused together into a new lifeform. To fuse two lifeforms, the first lifeform loses its first half genes and the second loses its last one-third genes. Then the resulting two gene chains are concatenated together into a single gene chain. For instance, the fusion of the two lifeforms [alpha, beta, gamma, alpha] and [delta, gamma, delta, beta] is [gamma, alpha, delta, gamma, delta]. When two lifeforms with different-length gene chains try to fuse, an exception should be raised. In response to the exception, the first lifeform is returned as the result of fusion.
When two lifeforms of equal-length gene chains mate, the first lifeform replaces its odd-numbered genes with the matching odd-numbered genes of the second lifeform. When two lifeforms with different-length gene chains try to mate, an exception should be raised. In response to the exception, the first lifeform is returned as the result of mating. For instance, when [alpha, alpha, beta, beta] and [gamma, beta, alpha, delta] mate, the child is [gamma, alpha, alpha, beta]. As another example, when [alpha, alpha, delta, delta] and [gamma, beta] mate, the child is [alpha, alpha, delta, delta].
Two lifeforms may also compete in this cruel evolution process. When two lifeforms compete, the one with the longer chain of genes wins, but the winner loses the first half of its genes. For instance, when [alpha, beta, gamma, delta, alpha] and [beta, beta, alpha, delta] compete, the resultant lifeform is [gamma, delta, alpha]. When two lifeforms with gene chains of the same length compete, the one with earlier lexical order of the gene chain win; in this case, the surviver loses its first one-third and last one-third genes in order to respect this harsh competition. For instance, when [alpha, beta, gamma, delta, alpha] and [beta, beta, alpha, delta, alpha] compete, the resultant lifeform is [beta, gamma, delta]. When two identical lifeforms compete, the resultant lifeform consists of a single gene which is the last gene of the original lifeform. For instance, when [alpha, beta, gamma, delta, alpha] and [alpha, beta, gamma, delta, alpha] compete, the resultant lifeform is [alpha].
The computation of "one-third" and "half" in the above description is taken with respect to integers. Note the resultant lifeform of a competition contains at least one gene.
You are expected to hand in an ML (or scheme) program in printed form and two test cases. In each test case, the two lifeforms have chains of at least 20 genes. You may either implement the fusion operation or you may make up two lifeforms with gene chains of length at least 20 and perform mutation, mating, and competition. Two sample lifeforms are [gamma, alpha, beta, gamma, alpha, alpha, beta, delta, delta, gamma, beta, alpha, beta, alpha, alpha, gamma, delta, alpha, delta, gamma] and [alpha, gamma, beta, alpha, delta, beta, gamma, beta, alpha, alpha, gamma, delta, delta, alpha, gamma, delta, beta, beta, alpha, gamma].
有五位小姐排成一列 所有的小姐穿的衣服顏色都不一樣 所有的小姐姓也不同 所有的小姐都養不同的寵物,喝不同的飲料,吃不同的水果 錢小姐穿紅色的衣服 翁小姐養了一隻狗 陳小姐喝茶 穿綠衣服的站在穿白衣服的左邊 穿綠衣服的小姐喝咖啡 吃西瓜的小姐養鳥 穿黃衣服的小姐吃柳丁 站在中間的小姐喝牛奶 趙小姐站在最左邊 吃橘子的小姐站在養貓的隔壁 養魚的小姐隔壁吃柳丁 吃蘋果的小姐喝香檳 江小姐吃香蕉 趙小姐站在穿藍衣服的隔壁 只喝開水的小姐站在吃橘子的隔壁請問那位小姐養蛇?
There will be two exams (25% each), paper homework (20%), and programming assignments (25%). Classroom discussion counts as 5% toward the final score.