Untitled

• Computer science is seen as the combination of mathematics and electrical engineering.
  • Electrical engineering provides the hardware.
  • Mathematics provides the theoretical foundation.
• Digital electronics involve gates, flip-flops, and memory.
• Reading and writing are synchronized using a clock, measured in Hz.
• Large software systems require theoretical foundations beyond digital electronics.
• Mathematics provides the language, ideas, notions, definitions, techniques, and results necessary for programming and computation.
• Programming languages derive functions, recursion, iteration, operators, variables, expressions, evaluation, numbers, types, sets, relations, tuples, structures, and graphs from mathematics.
• Operations such as arithmetic, Boolean, structural operations (on tuples, sets, etc.), abstraction, mapping, and folding are taken from mathematics.
• Mathematical objects do not have the same limitations as computers.
  • Computers approximate real numbers.
  • Computers cannot implement infinite tape (Turing machines).
  • Mathematical objects are cheaper than objects created on a physical computer.
• Functions are mappings that take no time to compute or evaluate.
• Knowing that an object exists is often all that is needed.

Interpreters

• An interpreter:
  • Written in a source language.
  • Compiled into a target language
  • Runs on a processor or another interpreter.

Interpreters and Programs

• Interpreters can execute programs compiled from another language.

OCaml

• OCaml is a functional, interactive programming language.
• Expressions are entered at the prompt and ended with ";;".

OCaml examples

## 3;;
- : int = 3
## "asdf";;
- : string = "asdf"
## 'm';;
- : char = 'm'
## 3.1415;;
- : float = 3.1415
## [1; 2; 3; 5; 8; 13];;
- : int list = [1; 2; 3; 5; 8; 13]
## [; [2; 3]; [4; 5; 6]];;
- : int list list = [; [2; 3]; [4; 5; 6]]

Modules in OCaml

• Modules aggregate functions and variables.
• Modules control visibility.
• Functionality is managed by loading and using modules.

Directives in OCaml

• Directives are commands that start with "#".
• Directives are non-programmable.
• Directives provide information and change the run-time system.

Useful directives include

• #list;; to list available modules
• #cd ;; to change to a directory
• #require ;; to specify that a module is required
• #show_module ;; to see the signature of the module
• #trace ;; to trace a function
• #untrace ;; to untrace a function

Finding Available Directives

• Find directives using Hashtbl.iter (fun k _v -> print_endline k) Toploop.directive_table;;
• A function can be defined to list directives:

let directives () =
    Hashtbl.iter
      (fun k _v -> print_endline k)
      Toploop.directive_table;;

• Run directives();; to see the list of directives.

Pervasives Module

• The Pervasives module contains built-in procedures in OCaml.
• Executing #show_module Pervasives;; shows the module's contents.

Lists

• Add an element to a list using :::

## 3 :: [4; 5; 6];;
- : int list = [3; 4; 5; 6]

• Append elements to a list using @:

## [2; 3] @ [5; 8; 13];;
- : int list = [2; 3; 5; 8; 13]

• #show_module List;; shows available list functions.

Functions

• Syntax available:
  • Named functions
  • Anonymous functions
  • Pattern-matching functions
  • Recursive functions
  • Mutually recursive functions

Function definition

• To define a function:

## let square n = n * n;;
val square : int -> int = 

• Use it like a built-in function:

## square;;
- : int -> int = 
## square 234;;
- : int = 54756
## square(34);;
- : int = 1156
## square 0;;
- : int = 0

• Parentheses are not ordinarily needed, but are sometimes required.

FOPL (First-Order Predicate Logic)

• FOPL is the language of exact sciences (mathematics & computer science).
  • Precise
  • Concise
  • Unambiguous
  • Language-neutral
  • Easy to check
• Used in calculus, discrete mathematics, algorithms, and compiler construction.
• FOPL is a good vehicle for testing student knowledge.
• Goal: Formalize statements.
  • Read sentences and grasp meaning.
  • Translate sentences from natural language into FOPL.

Syllogisms

• Syllogism definitions:
  • An argument-form for deductive reasoning.
  • Many syllogisms were discovered by Chrysippus of Soli (3rd century BC).
  • Presented in the form: assumption1, assumption2, ... ∴ conclusion
  • ∴ should be read as "therefore"

Modus Ponendo Ponens

• α, α→β ∴ β
• Example: It’s raining; If it’s raining, John carries an umbrella =⇒ John is currently carrying an umbrella

Modus Tollendo Tollens

• ¬β, α→β ∴ ¬α
• Example: John is not currently carrying an umbrella; If it’s raining, John carries an umbrella =⇒ It is currently not raining

Modus Tollendo Ponens

• Also known as Disjunctive Syllogism
• ¬α, α∨β ∴ β
• Example: The coffee is not black; Coffee is either black, or with milk =⇒ The coffee has milk

Modus Ponendo Tollens

• α, ¬(α ∧ β) ∴ ¬β
• Example: This food contains sugar; A food cannot both contain sugar and be dietetic =⇒ This food is not dietetic

Hypothetical Syllogism

• α→β ∴ ¬β → ¬α
• Example: If it’s raining, John carries an umbrella =⇒ If John is not carrying an umbrella, it is not raining

Double Negation

• ¬¬α ∴ α
• Example: It is not the case that this is not complicated =⇒ It is complicated