Notes of Programming Languages, Part A by Dan Grossman, University of Washington in Coursera.

command

C-x C-f: find file
C-x C-s: save
C-c C-s Enter, use “foo.sml” (Its type is unit and its result is () (the only value of type unit), but its effect is to include all the bindings in the file “foo.sml”)
not reusing use on a file without restarting the ERPL
C-d: exit
The REPL: Read-Eval-Print-Loop

Basic

SML Style Guide
The most important commands in Emacs
definitions for expressions: syntax, type-checking rules, evaluation rules
Variables are Immutable Bindings are immutable. Given val x = 8+9; we produce a dynamic environment where x maps to 17. In this environment, x will always map to 17; there is no “assignment statement” in ML for changing what x maps to. You can have another binding later, say val x = 19;, but that just creates a different environment where the later binding for x shadows the earlier one.
minus5: ~5
divide: x div y
Real.fromInt 2;: int -> real
= <> can be used with any “equality type” but not with real
Evaluation: A function is a value!
Pairs and Other Tuples

Lists

Usages

[] can have type t list list for any type
- SML uses type 'a list to indicate this (“quote a” or “alpha”)
e1::e2
null e evalueates to true if and only if e evaluates to []
- null : 'a list -> bool
If e evaluetes to [v1, v2,…, vn] then hd e evaluates to v1
- 'hd : 'a list -> 'a
- (raise exception if e evalutes to [])
If e evaluetes to [v1, v2,…, vn] then tl e evaluates to [v2, …, vn]
- tl : 'a list -> 'a list
- (raise exception if e evaluates to [])
- Notice result is a list

List Functions

use recursion

fun sum_list(xs : int list) =
  if null xs
  then 0
  else hd xs + sum_list(tl xs);
fun countdown(x : int) = (* [5,4,3,2,1] *)
  if x=0
  then []
  else x::countdown(x-1);
fun append(xs : int list, ys : int list) =
  if null xs
  then ys
  else (hd xs)::append((tl xs), ys);
fun firsts(xs : (int * int) list) = (* [(3,4),(5,6)] -> [3,5] *)
  if null xs
  then []
  else (#1 (hd xs))::firsts(tl xs);
(* [Reference](http://www3.cs.stonybrook.edu/~leo/CSE215/cse215FctProgramming.pdf) *)
(* return a list without element xs *)
fun remove(xs : int, ys : int list) =
  if null ys then []
  else if xs = hd ys then remove(xs, tl ys)
  else hd ys :: remove(xs, tl ys);
(* return a list without duplicate element *)
fun remove_duplicate(pr : int list) =
  if null pr then []
  else hd pr :: remove(hd pr, remove_duplicate(tl pr));

Let Expression

let b1 b2 ... bn in e end

Local val definitions need to be between let and in

Nested Functions

(* [1,2,3,4,5] *)
fun countup_from1_better(x : int) =
  let fun count(from : int) =
    if from = x
    then x::[]
    else from:: count(from+1)
  in
      count 1
  end;

Functions can use bindings in the environment where they are defined:

Binding from “outer” environments such as parameters to the outer function
Earlier bindings in the let-expression

Avoid Repeated Computation: Saving recursive results in local bindings is essential

fun max(xs : int list) = 
    if null xs
    then 0 (* horrible style *)
    else if null(tl xs)
    then hd xs
    else
        let val tl_ans = max(tl xs)
        in
            if hd xs > tl_ans
            then hd xs
            else tl_ans
        end

Options

Motivating Options Having max return 0 for the empty list is really awful
- Could raise an exception
- Could return a zero-element or one-element list
t option is a type for any type t
Building
- NONE has type 'a option
- SOME e has type t option if e has type t
Accessing
- isSome has type a option -> bool
- ‘valOf’ has type 'a option -> 'a (exception if given NONE)

(* better: returns an int option *)
(* fn: int list -> int option *)
fun max (xs : int list) = 
    if null xs
    then NONE
    else
        let val tl_ans = max(tl xs)
        in if isSome tl_ans andalso valOf tl_ans > hd xs
            then tl_ans
            else SOME (hd xs)
        end

In the above function, we call isSome tl_ans checking for none every time but none case is only for the empty list. The following version is a little cleaner.

fun max (xs : int list) = 
    if null xs
    then NONE
    else let (* fine to assume argument nonempty because it is local *)
            (* int list -> int *)
            fun max_nonempty (xs : int list) = 
                if null (tl xs) (* xs better not be [] *)
                then hd xs
                else let val tl_ans = max_nonempty(tl xs)
                    in
                        if hd xs > tl_ans
                        then hd xs
                        else tl_ans
                    end
        in
            SOME (max_nonempty xs)
        end

run:

- max [3,7,5];
val it = SOME 7 : int option
- max [];
val it = NONE : int option

Lack of Mutation and Benefits Thereof

In ML, there is no way to change the contents of a binding, a tuple, or a list. If x maps to some value like the list of pairs [(3,4),(7,9)] in some environment, then x will forever map to that list in that environment. There is no assignment statement that changes x to map to a different list.
Having immutable data is probably the most important “non-feature” a anguage can have, and it is one of the main contributions of functional programming.
A big advantages to immutable data: it makes sharing and aliasing irrelevant

The Pieces of a Programming Language

Five different things

Syntax: How do you write language constructs?
Semantics: What do programs mean? (Evaluation rules)
Idioms: What are typical patterns for using language features to express your computation?
Libraries: What facilities does the language(or a well-known project) provide “standard”:
Tools: What do language implementations provide to make your job easier?

Section2

Conceptual Ways to Build New Types

Base types: int bool unit char…
Compound types: tuples lists options…
Any decent programming language provides these building blocks in some way:

“Each-of”: A compound type t describes values that contain each of values of type t1, t2, …, and tn.
“One-of”: A compound type t describes values that contain a value of one of the types t1, t2, …, or tn.
“Self-reference”: A compound type t may refer to itself in its definition in order to describe recursive data structures like lists and trees.
tuples are particular ways of writing paticular records
Example:
Tuples build each-of types: int * bool contains an int and a bool
Options build one-of types: int option contains an int or it contains no data
Lists use all three building blocks: int list contains an int and another int list or it contains no data
Records: Another Approach to “Each-of” Types
Record values have fields (any name) holding values {f1 = v1, ..., fn = vn}
Record types have fields (and name) holding values {f1 : t1, ..., fn : tn}
The order of fields in a record value or type never matters (REPL alphabetizes fields just for consistency)
Building records: {f1 = e1, ..., fn = en}
Accessing pieces: #myfieldname e

By Name vs. By Position, Syntactic Sugar, and The Truth About Tuples

Records are “by name” and tuples are “by position.”
(e1, ..., en) is another way of writing {1=e1, ..., n=en}
t1*...*tn is another way of writing {1:t1, ..., n:tn}
“Tuples are just syntactic sugar for records with field named 1, 2, …, n”

Datatype Bindings: Our Own “One-of” Types

Datatype bindings, our third kind of binding after variable bindings and function bindings
Build datatype values

1
2
3

datatype mytype = TwoInts of int * int
                  | Str of string
                  | Pizza

Adds a new type mytype to the environment
Adds constructors to the environment: TwoInts, Str and Pizza
A constructor is (among other things), a function that makes values of the new type (or is a value of the new type):

1
2
3

TwoInts : int * int -> mytype
Str : string -> mytype
Pizza : mytype

Access a datatype value

Check what variant it is (what constructor made it) <- null and isSome
Extract the data (if that variant has any) <- hd, tl and valOf