Programming Languages (1)¶

Enter your name and student ID.

  • Name:
  • Student ID:

1. Choose your language¶

Choose a language you want to work on for today from the following.

  • Go --- designed as a "better C"

  • Julia --- popular for scientific computing

  • OCaml --- a practical functional language

  • Rust --- a system programming language with memory safety without garbage collection

  • Choose a language you want to learn instead of one you already know.

  • The choice you made for today is not final, however; the language you work on in the rest of the course will be determined based on your preference as well as the balance.

Declare your choice in the following cell. You can write any number of languages you actually worked on. In this notebook, I will work on the following language(s).

BEGIN SOLUTION END SOLUTION

2. Prepare¶

  • Find an authoritive documentation for the language you chose by Google (e.g., google with [the language name documentation])

  • I recommend you to find them by yourself, but in case you have a hard time finding it, here they are

  • Go:

  • Julia:

  • OCaml:

  • Rust: language manual and other docs

3. Roadmap¶

  • In this notebook, you will learn most basic elements of virtually all programming languages
  • You will find the following a useful recipe when learning a new programming language

4. Defining functions¶

  • Defining a function is probably the most basic yet most important tool for any programming language

Problem 1 : ¶

  • In the language you chose, write a function f that takes a number $x$ and return $x + 1$. i.e.,

$$ f(x) = x + 1 $$

  • In cells that follow, choose your language from the language selection menu.

解答セル/Answer Cell

Go

In [ ]:
func f(x int) int {
        return x + 1
}

Julia

In [ ]:
function f(x)
    x + 1
end

OCaml

In [ ]:
let f x = x + 1
;;

Rust

In [ ]:
fn f(x: i32) -> i32 {
        return x + 1
}

and compute ${\tt f}(3)$.

解答セル/Answer Cell

Go

In [ ]:
f(3)

Julia

In [ ]:
f(3)

OCaml

In [ ]:
f 3
;;

Rust

In [ ]:
f(3)

5. Recursive function¶

  • A recursive function is simply a function that calls itself
  • If there is one thing that makes a programming language different from a calculator, it is a recursive function

Problem 2 : ¶

  • Using a recursive definition of a function fib that takes an integer $n$ and return the $n$th fibonacci number $f_n$ defined as follows

$$ f_n = \left\{\begin{array}{ll} 1 & (n < 2) \\ f_{n-1} + f_{n-2} & (n \geq 2) \end{array} \right. $$

  • Note: for the purpose of today, it suffices to write a straightforward recursive function; never mind the efficiency (time complexity) of the algorithm; you do not have to do use loops to make it linear time

解答セル/Answer Cell

Go

In [ ]:
func fib(n int) int {
        if n < 2 {
                return 1
        } else {
                return fib(n - 1) + fib(n - 2)
        }
}

Julia

In [ ]:
function fib(n :: Int)
    if n < 2
        1
    else
        fib(n - 1) + fib(n - 2)
    end
end

OCaml

In [ ]:
let rec fib n =
  if n < 2 then
    1
  else
    fib (n - 1) + fib (n - 2)
;;

Rust

In [ ]:
fn fib(n: i32) -> i32 {
    if n < 2 {
        1
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

and compute ${\tt fib}(10)$. It must be 89.

解答セル/Answer Cell

Go

In [ ]:
fib(10)

Julia

In [ ]:
fib(10)

OCaml

In [ ]:
fib 10

Rust

In [ ]:
fib(10)

6. Variables¶

  • A variable is a tool to "remember" an intermediate result of a computation
  • It is useful to make programs easier to read (by breaking otherwise long expressions into a series of small expressions) and more efficient (by avoiding repeated computations)

Problem 3 : ¶

  • Learn how to introduce a new variable and define fib2 that does exactly the same computation as fib, but with variables; specifically, compute $f_{n-1} + f_{n-2}$ by $x = {\tt fib2}(n-1)$, $y = {\tt fib2}(n-2)$, and then compute $x + y$.

解答セル/Answer Cell

Go

In [ ]:
func fib2(n int) int {
        if n < 2 {
                return 1
        } else {
                x := fib2(n - 1)
                y := fib2(n - 2)
                return x + y
        }
}

Julia

In [ ]:
function fib2(n :: Int)
  if n < 2
      1
  else
      x = fib2(n - 1)
      y = fib2(n - 2)
      x + y
  end
end

OCaml

In [ ]:
let rec fib2 n =
  if n < 2 then
    1
  else
    let x = fib2 (n - 1) in
    let y = fib2 (n - 2) in
    x + y
;;

Rust

In [ ]:
fn fib2(n: i32) -> i32 {
    if n < 2 {
        1
    } else {
        let x = fib2(n - 1);
        let y = fib2(n - 2);
        x + y
    }
}

and compute ${\tt fib2}(10)$. It must be 89.

解答セル/Answer Cell

Go

In [ ]:
fib2(10)

Julia

In [ ]:
fib2(10)

OCaml

In [ ]:
fib2 10

Rust

In [ ]:
fib2(10)

7. Defining types¶

  • In programming languages, a type generally means a set of values having the same or similar properties or applicable operations

  • Basic examples are integers, floating point numbers, strings, etc.

  • Programming languages allow you to define a new type built from existing types

  • e.g., define a complex number as a pair of real numbers (real and imaginary part)

  • Different languages have different names/mechanisms to compose a new type from existing types

    • C : struct
    • C++ : struct/class
    • Python : class
    • Go : struct
    • Julia : struct
    • OCaml : tuples, records, object (class)
    • Rust : struct

Problem 4 : ¶

  • Learn how to define a new composite type in the language you chose;
  • define a new type representing a person (named person or Person depending on the naming constraint/convention of the language), which consists of the name (string) and the date of birth (string);

解答セル/Answer Cell

Go

In [ ]:
type Person struct {
        name string
        date_of_birth string
}

Julia

In [ ]:
struct Person
    name :: String
    date_of_birth :: String
end

OCaml

In [ ]:
type person =
  Person of (string * string)
;;

Rust

In [ ]:
struct Person {
    name: String,
    date_of_birth: String
}
  • define a function called person_name that takes a person and returns his/her name;
  • create a person whose name is "Masakazu Mimura" (date of birth = 1967/6/8) and apply person_name to it

解答セル/Answer Cell

Go

In [ ]:
func person_name(p Person) string {
        return p.name
}
person_name(Person{"Masakazu Mimura", "1967/6/8"})

Julia

In [ ]:
function person_name(p :: Person)
    p.name
end

person_name(Person("Masakazu Mimura", "1967/6/8"))

OCaml

In [ ]:
let person_name p =
  match p with
    Person(name, dob) -> name
;;
person_name (Person("Masakazu Mimura", "1967/6/8"))
;;

Rust

In [ ]:
fn person_name(p : Person) -> String {
        return p.name
}
person_name(Person{name: String::from("Masakazu Mimura"),
                   date_of_birth: String::from("1967/6/8")})

8. Recursive types¶

  • Just as a function can be recursive, so can a type
  • A recursive type is a type one of whose component has the same type as itself
  • It is the basis for defining data structures that can grow arbitrarily large, such as trees, lists, and graphs

Problem 5 : ¶

  • Define a type that represents a binary tree
  • More specifically, a binary tree is either
    • empty,
    • or a node having two children each of which is a binary tree (note that a child may be empty)

解答セル/Answer Cell

Go

In [ ]:
type Bintree struct {
        left * Bintree
        right * Bintree
}

Julia

In [ ]:
struct Bintree
    left :: Union{Nothing,Bintree}
    right :: Union{Nothing,Bintree}
end

OCaml

In [ ]:
type bintree =
  Empty
| Node of (bintree * bintree)
;;

Rust

In [ ]:
enum Bintree {
    Empty,
    Node { left: Box<Bintree>, right: Box<Bintree> }
}

Problem 6 : ¶

  • Define a function mk_tree that takes an integer $n$ and returns the "maximally balanced binary tree" that has exactly $n$ nodes
  • A binary tree $t$ is maximally balanced when $t$'s left child has exactly the same as or just one more nodes than $t$'s right child
  • Given $n$, the maximally balanced binary tree of $n$ nodes is unique

解答セル/Answer Cell

Go

In [ ]:
func mk_tree(n int) * Bintree {
        if n > 0 {
                rc := (n - 1) / 2
                lc := n - 1 - rc
                return &Bintree{mk_tree(lc), mk_tree(rc)}
        } else {
		var p * Bintree = nil
		return p
	}
}

Julia

In [ ]:
function mk_tree(n :: Int)
    if n == 0
        nothing
    else
        rc = div(n - 1, 2)
        lc = n - 1 - rc
        Bintree(mk_tree(lc), mk_tree(rc))
    end
end

OCaml

In [ ]:
let rec mk_tree n = 
  if n = 0 then
    Empty
  else
    let rc = (n - 1) / 2 in
    let lc = n - 1 - rc in
    Node(mk_tree lc, mk_tree rc)
;;

Rust

In [ ]:
fn mk_tree(n: i32) -> Bintree {
    if n == 0 {
        Bintree::Empty
    } else {
        let rc = (n - 1) / 2;
        let lc = n - 1 - rc;
        Bintree::Node{left: Box::new(mk_tree(lc)),
                      right: Box::new(mk_tree(rc))}
    }
}

Problem 7 : ¶

  • Define a function count_nodes that takes a binary tree and returns the number of nodes in it

解答セル/Answer Cell

Go

In [ ]:
func count_nodes(t * Bintree) int {
        if t == nil {
                return 0
        } else {
                return 1 + count_nodes(t.left) + count_nodes(t.right)
        }
}

Julia

In [ ]:
count_nodes(t :: Nothing) = 0
count_nodes(t :: Bintree) = 1 + count_nodes(t.left) + count_nodes(t.right)

OCaml

In [ ]:
let rec count_nodes t =
  match t with 
    Empty -> 0
  | Node(l, r) -> 1 + count_nodes l + count_nodes r
;;

Rust

In [ ]:
fn count_nodes(t: Bintree) -> i32 {
    match t {
        Bintree::Empty => 0,
        Bintree::Node{left, right} =>
            1 + count_nodes(*left) + count_nodes(*right)
    }
}

Problem 8 : ¶

  • Obviously, for $t = {\tt mk\_tree}(n)$, ${\tt count\_nodes}(t)$ should return $n$
  • Confirm this for meaningfully large $n$ (e.g., 1000)

解答セル/Answer Cell

Go

In [ ]:
count_nodes(mk_tree(1000))

Julia

In [ ]:
count_nodes(mk_tree(1000))

OCaml

In [ ]:
count_nodes (mk_tree 1000)
;;

Rust

In [ ]:
count_nodes(mk_tree(1000))