CS320 Summer I 2010 TF

This is the teaching fellow's page for course CS 320 Concepts of Programming Languages. I will post related material here from time to time so that both students and professor can keep track of updated info about the discussion session.
General Information
Instructor: Hongwei Xi
Teaching Assistant: Zhiqiang Ren
  Office hour: 1:30 - 3:00 PM Mon, 1:30-3:00 PM Thu, MCS 178
  Lab Session: 2:00 - 3:00 PM Wed, MCS 148
Working With CS Computing Resources
See the Getting Started (thanks to Likai) guide for tips on working from home and transferring files over, and for a primer on using Linux. There is no need to follow these instructions if you are familiar with Linux, they are for your reference only. If you are an BU student, you can get X-Win32 here.

Jun. 23rd. 2010

posted Jun 23, 2010, 12:13 PM by Zhiqiang Ren   [ updated Jun 23, 2010, 12:40 PM ]

1. In functional programming language, we can only bind a name with a value. We cannot modify a value. There is one exception: we can modify the content of the reference.
2. $delay can help us contruct the type stream, but that's not enough. Use $delay correctly to delay the recursive call.
3. Use abst@ype ans to check whether your implementation is in Continuation Parsing Style.

Jun. 16th. 2010

posted Jun 16, 2010, 12:13 PM by Zhiqiang Ren   [ updated Jun 16, 2010, 1:05 PM ]

1. Implementing algorithm in a recursive style usually results in better performance (scaling down the problem and conquer it).
2. Using exception or option smartly.
3. By using reference, we can modify the object instead of creating a new one.
4. The type of "ref int" is itself a boxed type.

June 9th. 2010

posted Jun 9, 2010, 12:28 PM by Zhiqiang Ren   [ updated Jun 9, 2010, 1:18 PM ]

1. lambda is function (closure) without name.
2. closure is a package containing a function and some extra arguments to this function as well.
3. You can think of continuation as a chain of closures.
    Continuation style saves memory from stack but consumes memory from heap.
    main.cpp is an implementation of factorial in C/C++ using closure and continuation parsing style.
    Call the previous continuation only once at the end of the function body, otherwise you will end up with a fake continuation style.
    Refer to the list_tree_op.dats of the post on June 2nd. as a demo for transforming tree to list using continuation.
4. Do the type checking from time to time. Use extern keyword to declare the function.

5. If you have further questions about the mid-term 1, feel free to discuss with me.

Solution to assignment 02

posted Jun 6, 2010, 3:53 PM by Zhiqiang Ren   [ updated Jun 6, 2010, 4:01 PM ]

The compressed file "homework.tar.gz" contains all the files of the solution to assignment 02. To uncompress it, run as follows
>>tar xzvf homework.tar.gz
A folder called "homework" containing all the files will show up in your current folder.

June 2nd. 2010

posted Jun 2, 2010, 12:22 PM by Zhiqiang Ren   [ updated Jun 2, 2010, 3:16 PM ]

1. Tail recursion is preferred when processing a list from left to right. The result may be not in the order we want. Apply the reverse if necessary before or after the processing. Append operation is in O(n). If it is used in other algorithm, the total will probably turns out to be O(nx) (x >= 2). Try avoiding append operation.

2. Using high order function to make your code flexible dynamically.

3. Implementing tail recursive function to traverse a tree is difficult but possible with the help of closure. Check the implementation in closure.dats. If you cannot understand it now, don't be anxious. There is no need for you to write code in this way. Don't use tail-recursive just for the purpose of tai-recursive. It saves the space on stack, but it also consume space on the heap.

4. Try Koch snowflake.

6. Correction: I said we cannot declare reference in function. This is not correct at all. Check closure.dats to see how to use reference with closure.

May 26th. 2010

posted May 26, 2010, 12:26 PM by Zhiqiang Ren   [ updated May 26, 2010, 12:45 PM ]

Tail-recursive functions save the space and time of your Machine.
Don't be afraid of writing tail-recursive functions. Write a "while" statement and transform it into recursive function. Make up your mind which variables will be modified by the "while" statement. Those are the arguments as well as the return value of the recursive function.
Using template method to achieve generics will generate executable larger than that generated by using parametric polymorphism method, but it can save the running time to certian extent.

Homework 1

posted May 19, 2010, 6:00 PM by Zhiqiang Ren   [ updated May 19, 2010, 6:00 PM ]

Homework 1 exercise 4 is typeset into PDF and attached below.

May 19th. 2010

posted May 19, 2010, 12:55 PM by Zhiqiang Ren   [ updated May 19, 2010, 1:13 PM ]

  • Compiling and running ATS programs.
    • ATS compiles .dats into C code, then invokes GCC to compile the C code to executable. A makefile is given out (see attachment) to ease your life with ATS.
    • ATS is already installed on csa2. Refer to previous post about how to use it. Or you can install ATS on your own system according to the previous posts. 
  • You have if...then...else, but you do not have while. Use recursive function to replace while.
  • You have tuple and record, both of which have two versions: box and flat.
  • You have list0, see $ATSHOME/prelude/SATS/list0.sats to find the library functions you need to manipulate list0.
  • rational.sats, rational.dats and test_rational.dats provide a demo of project in ATS with multiple files.

How to install Cairo on your system

posted May 18, 2010, 9:34 PM by Zhiqiang Ren   [ updated May 18, 2010, 9:43 PM ]

If you want to use ATS to draw picures shown in class today, Cairo (including libraries and header files) should be installed on your system. On many systems including csa2, Cairo has already been installed. So you can just neglect this post. If it is not true (ATS compiler complains that no file of cairo can be found.), please refer to this page to learn how to install Cairo on your own system. It is very easy. E.g. if your system is debian or ubuntu, all you have to do is to execute the following:
>>sudo apt-get install libcairo2-dev

How to use ATS installed on csa2.bu.edu

posted May 18, 2010, 9:07 PM by Zhiqiang Ren   [ updated May 20, 2010, 6:55 PM ]

ATS 0.2.0 has been installed on csa2 and csa3. But you need to modify your environment variables so that you can use it. What you have to do is to add the following to the file .bash_profile under your home directory
ATSHOME=/usr/local/ats/lib/ats-anairiats-0.2.0; export ATSHOME

PATH=/usr/local/ats/bin:$PATH; export PATH
And then relog into the csa2.

1-10 of 12