Lecture 1 

Course overview

--- 

adminitrative
 webpage: ~/lliao/cis670
 email: lliao@cis.udel.edu
 instructor: Li Liao
 office hours: TR 1:30-3:00pm
 TA: Ilknur Aydin

- grading: hw 40%, mid-term 25%, and final 35%
required test: "Programming language pragmatics" by Michael Scott

- late policy: no later than one week. 20% penalty 24hrs past due time.

- academic dishoesty 
  (http://www.udel.edu/stuhb/01-02/campuslife/policy1.html#dishonesty)

- syllabus (handout)

- roster (attendance)
  o circulate a piece of blank paper for students 
     to write down their name and email

---

What langugage?

I was asked by a friend about what course I would be teaching,
and I told him it was "programming language". Then my friend
asked: what language you gonna teach? To tease him, I said:
just programming language. My friend, who is a quite savvy programmer, 
insisted: what programming language, C? I said: no. "C++?" he said. 
"No" I said.

So, this class is not about learning any specific programming language.
It is not about crafting a compiler either.
Rather, it is about the study of programming languages in general: 
concepts, principles, and pragmatics.

Try to look at things from the following perspective:

- science (or math): 
    Turing complete, Chomsky's theory on grammar, Lambda calculus, ...

- engineering: 
    Garbage collection, ...

- human factors: 

---

The intrinsic tension between two aspects of programming language

- To formulate computation 
    (Expressiveness, ..., -> high level languages)

  o Turing completeness
  o Language classes (syntax)
     > Regular expression
     > Context-free
     > Context-sensitive
  o Ability of abstraction: to form new vocabularies -> more expressive

- To instruct a real computer what to do? 
    (efficiency, ..., -> machine language)
  o implement contructs of a high level language
     > e.g., activation record (stack) for subroutines


Bottom line: any high level language has to run by a real computer 
   in silicon (at least for now)
   => assembler, interpreter, compiler.

Compilation vs. Interpretation

- compiler: 
     source program in high level language 
        => target program in machine language 
           (then executed by a real machine)

- interpreter: 
     source program in high level language 
        => execute right away (by a emulated machine)

- hybrid:
   o virtual machine (Java VM)
   o scripting language (PERL)

Quiz: True or false?
  1) a scripting language is always interpreted
  2) an interactive language is always interpreted
  3) compiler always generates target program in machine language
  4) how is it possible for a compiler to have be written in
     the language that it need to compile?

   o Pascal bootstrapping
     > Pascal compiler, written in Pascal, -> p-code
     > same compiler, already translated into p-code
     > p-code interpreter written in Pascal

---

- Lexical and sytax analysis
  o Tokens
  o Grammars
    > Ambiguity
  o Parse trees
    > Recursive descent

- Semantic analysis and intermediate code generation/interpretation 
  o Abstract Syntax Tree (AST)
  o Name, scoping
  o control flow
  o subroutines
  o ...

  o interpreter 


- Target code generation (code improvement)
  o CISC, RISC
  o instruction sets of assembly language
  o Garbage collection

---

ML

- why chose ML?
 o a different (and to you probably new) paradigm: Functional programming
   ML is a strict, statically typed functional programming language with
    modular structure.
 o esp. good as meta language for language manipulation, e.g.,
    writing interpreters with elegancy. 

- ML core language

- Access ML
  o install on your own PC, or
  o from your acad account 
    > add to your path "/usr/local/smlnj/bin"
    > type "sml" to launch a session
    > Ctrl z to end a session

- First encounter with SML

  Once you enter SML, the system will display one line like 

"Standard ML of New Jersey v110.41 [FLINT v1.5], July 05, 2002"

  and a new blink line starting with "-" to prompt you for input.
  Such an interactive interface environment may be familier to you.
  But do not mistake this "read-eval-print" as a necessary indication of
  interpreter.

  What you type after SML prompt "-" should be valid SML expressions.
  If your expression is too long to fit into one line on your screen, 
  you simple use catridge return to start a new line, and of course, the
  new line will automatically start with "=". Type a semicolon to 
  tell SML start to evaluate.

  - 2;
  val it = 2: int
  - 3.2415
  - ;
  val it = 3.1415 : real
  - true;
  val it = true : bool
  - "hello world";
  val it = "hellow world" : string
  - #"C"
  val it = #"C" : char

  
  The evaluation result starts with "val", indicating the value to which your
  input expression(s) is evaluated. In the examples above, we input only 
  constants (be it integer, real number, boolean, string or char), SML calls
  the output value "it" and tells you what it equals to.

  You can treat "it" as a name and refer to it. For example,

  - 2;
  val it = 2 : int
  - it + 3;
  val it = 5 : int

  Following the output value is its type, delimited by ":".

  You can also declare a name. For example,

  - val pi = 3.1415;
  val pi = 3.1415 : real

  You can define a function (with a name). For example,

  - fun area (r) = pi * r * r;
  val area = fn : real -> real

  and call your function as following.

  - area (2.0);
  val it = 12.566 : real

  - area (2);
  stdIn:7.1-7.9 Error: operator and operand don't agree [literal]
  operator domain: real
  operand:         int
  in expression:
    area 2

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:52.48-52.56
             ../compiler/TopLevel/interact/evalloop.sml:35.55


  The function "area" takes a real number. In the example above, an integer
  is fed as argument. SML detected this mismatch and raised an exception.

  The built-in arithmetic operators "+, *, -, <, >, <=" and "=>" are
  overloaded, namely, can be applied to both real numbers and integers.

  You can write your SML program by any your favorite editor, be it "vi" or
  "emacs", and save into a file, say, "myprog.sml" (note: the extention
   .sml is not necessary.) Then under SML prompt, type
  
  - use "myprog.sml";
  
  SML will load the file and evaluate the program in it.


  SML uses recursion (it does have some imperative features and you are
   restricted from using them for some of your assignments)

  - fun fact(n) =
       if n = 0 then 1
       else n * fact(n-1);

  SML has type checking (inference) and polymorphism.

  - fun swap (x:int, y:int) =
      (y, x);

    val swap = fn : int * int -> int * int

  - fun swap (x, y) = (y, x);

    val swap = fn : 'a * 'b -> 'b * 'a

  - swap(false, 1.0);
    val it = (1.0,false) : real * bool

  Curried function

  - fun swap x y = (y, x);
    val swap = fn : 'a -> 'b -> 'b * 'a

  You can pass arguments to the function in different stages

  - fun add (x, y) = x+y;
    val add = fn: int*int -> int

  - fun add x y = x+y;
    val add = fn: int -> int -> int
                        (          ) 

  - val add5 = add 5;
    val add5 = fn: int -> int

  - add5 7;
    val it = 12 : int

  For 3 arguments, there are 4 versions of passing arguments: 

    int*int*int -> int
    int -> int -> int -> int
    int*int -> int -> int
    int -> int*int -> int


  - Compiler.Control.Print.printLength := 1000;
  - Compiler.Control.Print.printDepth := 10;