CS计算机代考程序代写 scheme python ocaml data structure javascript jvm c/c++ Lambda Calculus compiler Java flex F# c++ c# Erlang Haskell concurrency interpreter Introducing Haskell

Introducing Haskell

CSI3120 A

1

Programming Language Concepts

• Slides copyright
2017-2021

• Author David
Walker, updated by Amy
Felty

• permission granted
to reuse these slides for
non-commercial
educational purposes

Acknowled
gement

• An introduction to programming language concepts
• An introduction to OCaml
• Types and functional programming
• Inductive data types
• Polymorphic higher-order programming
• Data abstraction and modularity
• Mutable data and imperative programming
• Object-oriented programming
• Syntax and semantics
• Scope, procedures, and storage management
• Control in sequential languages
• Concurrent and distributed programming
• Combinators, pipelines, and scripting
• Semantics revisited

Overview of the course

Announc
ement

Change in lab – remote

Lab form – due Sept 25
(to be filled by student
who cannot aatend in
person class)

Midterm poll

In 1936, Alonzo Church invented
the lambda calculus. He called
it a logic, but it was a language
of pure functions — the world’s
first programming language.

He said:

“There may, indeed, be other
applications of the system than
its use as a logic.”

Alonzo Church, 1903-1995
Princeton Professor, 1929-1967

5

In 1936, Alonzo Church invented
the lambda calculus. He called
it a logic, but it was a language
of pure functions — the world’s
first programming language.

He said:

“There may, indeed, be other
applications of the system than
its use as a logic.”

Greatest technological
understatement of the 20th

century?

Alonzo Church, 1903-1995
Princeton Professor, 1929-1967

6

Vastly Abbreviated FP Geneology

LCF Theorem
Prover (70s)

Edinburgh ML

Miranda (80s)

Haskell
(90s – now)

Standard ML
(90s – now) OCaml

(90s – now)

Caml
(80s-now)

F#
(now)

LISP
(50s-now)

Scheme
(70s-now)

lazy

typed, polymorphic

untyped

Coq
(80s – now)

dependently
typed

call-by-value

Racket
(00s-now)

Scala
(00s – now)

7

Vastly Abbreviated FP Geneology

LCF Theorem
Prover (70s)

Edinburgh ML

Miranda (80s)

Haskell
(90s – now)

Standard ML
(90s – now) OCaml

(90s – now)

Caml
(80s-now)

F#
(now)

LISP
(50s-now)

Scheme
(70s-now)

lazy

typed, polymorphic

untyped

Coq
(80s – now)

dependently
typed

call-by-value

Racket
(00s-now)

Scala
(00s – now)

8

Functional Languages: Who’s using them?

F# in Visual Studio

map-reduce in their data centers

Erlang for
concurrency,
Haskell for
managing PHP

Haskell to
synthesize hardware

Scala for
correctness, maintainability, flexibility

www.artima.com/scalazine/articles/twitter_on_scala.html
www.janestreet.com/technology/
https://devblogs.microsoft.com/dotnet/tag/visual-f/
ai.google/research/pubs/pub62
www.haskell.org/haskellwiki/Haskell_in_industry
blogs.wsj.com/cio/2014/02/24/facebook-whatsapp-messaging-service-written-in-exotic-erlang/

Haskell
for specifying
equity derivatives

mathematicians

Coq (re)proof of
4-color theorem

9

http://www.artima.com/scalazine/articles/twitter_on_scala.html
http://www.janestreet.com/technology/
https://devblogs.microsoft.com/dotnet/tag/visual-f/
https://ai.google/research/pubs/pub62
http://www.haskell.org/haskellwiki/Haskell_in_industry
https://blogs.wsj.com/cio/2014/02/24/facebook-whatsapp-messaging-service-written-in-exotic-erlang/

Functional Languages: Join the crowd

• Elements of functional programming are showing up all over

– F# in Microsoft Visual Studio

– Scala combines ML (a functional language) with Objects

• runs on the JVM

– C# includes “delegates”

• delegates == functions

– Python includes “lambdas”

• lambdas == more functions

– Javascript

• find tutorials online about using functional programming
techniques to write more elegant code

– C++ libraries for map-reduce

• enabled functional parallelism at Google

– Java has generics and GC

– … 10

A Functional Review

11

Thinking Functionally

In Java or C, you get (most) work done by changing something

In ML, you get (most) work done by producing something new

temp = pair.x;
pair.x = pair.y;
pair.y = temp; commands modify or change an

existing data structure (like pair)

let
(x,y) = pair

in
(y,x)

you analyze existing data (like pair)
and you produce new data (y,x)

12

Thinking Functionally

imperative code:

• outputs are irrelevant!

• output is not function of input

• data properties change

• unrepeatable

• parallelism hidden

• harder to test

• harder to compose

pure, functional code:

• outputs are everything!

• output is function of input

• data properties are stable

• repeatable

• parallelism apparent

• easier to test

• easier to compose

temp = pair.x;
pair.x = pair.y;
pair.y = temp;

let (x,y) = pair in
(y,x)

13

OCaml Feature Overview

Small core based on the lambda calculus.

– Control is based on (recursive) functions.

– Instead of for-loops, while-loops, do-loops, iterators, etc.

• can be defined as library functions

– Makes it easy to define semantics

Supports first-class, lexically-scoped, higher-order procedures

– a.k.a. first-class functions or closures or lambdas

– first-class: functions are data values like any other data value

• like numbers, they can be stored, defined anonymously, …

– lexically-scoped: meaning of variables determined statically

– higher-order: functions as arguments and results

• programs passed to programs; generated from programs

These features also found in Racket, Haskell, SML, F#, Clojure, ….
14

OCaml Feature Overview

Statically typed: debugging and testing aid

– compiler catches many silly errors before you can run the code

• A type is worth a thousand tests (start at 6:20):

– https://www.youtube.com/watch?v=q1Yi-WM7XqQ

– Java is also strongly, statically typed

– Python, Javascript, etc. are all strongly, dynamically typed – type
errors are discovered while the code is running

Strongly typed: compiler enforces type abstraction

– cannot cast an integer to a record, function, string, etc.

– C/C++ are weakly-typed (statically typed) languages. The compiler
will happily let you do something smart (more often stupid).

Type inference: compiler fills in types for you

15

Running OCaml

• OCaml comes with compilers:

– “ocamlc” – fast bytecode compiler

– “ocamlopt” – optimizing, native code compiler

– “ocamlbuild” – a nice wrapper that computes dependencies (not used
in this course)

• And an interactive, top-level shell (interpreter):

– useful for trying something out, and for debugging small programs

– “ocaml” at the prompt

– You will likely use this most of the time.

• And many other tools

– e.g., debugger, dependency generator, profiler, etc.

• We will use it via VCL. You may want to try to install it yourself.

– See OCaml.org

16

Editing OCaml Programs

• Many options:
– Emacs

• what I’ll be using in labs, and what is available via VCL

• good support for OCaml with the Tuareg Emacs Mode

• powerful text editor, can run OCaml inside it

• (extensions written in elisp – a functional language!)

– OCaml IDE
• integrated development environment written in OCaml

• I haven’t used it, so can’t comment.

– Eclipse
• I haven’t tried it but others recommend it. See the information on

Brightspace added by TAs (in “Course Software” module, “Tips and
Advanced Alternatives” submodule).

– Sublime, atom
• I haven’t tried it, but many students have used it.

17

AN INTRODUCTORY EXAMPLE
(OR TWO)

18

OCaml Compiler and Interpreter

• Demo:

– emacs

– .ml files

– writing simple programs: hello.ml, sumTo.ml

– ocaml interpreter

– ocamlc compiler

19

A First OCaml Program

hello.ml:

print_string “Hello CSI 3120!!\n”;;

20

print_string “Hello CSI 3120!!\n”

A First OCaml Program

hello.ml:

a function its string argument
enclosed in “…”

a program
can be nothing
more than
just a single
expression
(but that is
uncommon)

no parens. normally call a function f like this:

f arg

(parens are used for grouping, precedence
only when necessary) 21

A First OCaml Program

$ ocaml

OCaml Version 4.05.0

# 3 + 1;;

– : int = 4

#

hello.ml:

interpreting and playing with hello.ml:

print_string “Hello CSI 3120!!\n”

the OCaml
interpreter

22

Current
versions of
OCaml on
website are
4.05 to 4.11
(depends
on OS)

A First OCaml Program

$ ocaml

OCaml Version 4.05.0

# 3 + 1;;

– : int = 4

# #use “hello.ml”;;

hello CSI 3120!!

– : unit = ()

#

hello.ml:

interpreting and playing with hello.ml:

print_string “Hello CSI 3120!!\n”

the OCaml
interpreter

23

Current
versions of
Ocaml on
website are
4.05 to 4.08
(depends
on OS)

A First OCaml Program

$ ocaml

OCaml Version 4.05.0

# 3 + 1;;

– : int = 4

# #use “hello.ml”;;

hello CSI 3120!!

– : unit = ()

# #quit;;

$

hello.ml:

interpreting and playing with hello.ml:

print_string “Hello CSI 3120!!\n”

the OCaml
interpreter

24

Current
versions of
Ocaml on
website are
4.05 to 4.08
(depends
on OS)

https://try.ocamlpro.com/

https://try.ocamlpro.com/

A First OCaml Program

print_string “Hello CSI 3120!!\n”

$ ocamlc hello.ml

$

hello.ml:

compiling and running hello.ml:

the OCaml
compiler

25

A First OCaml Program

print_string “Hello CSI 3120!!\n”

$ ocamlc hello.ml

$ ocaml

OCaml Version 4.05.0

#

hello.ml:

compiling and running hello.ml:

the OCaml
compiler

26

A First OCaml Program

print_string “Hello CSI 3120!!\n”

$ ocamlc hello.ml

$ ocaml

OCaml Version 4.05.0

# #load “hello.cmo”;;

Hello CSI 3120!!

#

hello.ml:

compiling and running hello.ml:

the OCaml
compiler

27

(* sum the numbers from 0 to n

*)

let rec sumTo (n:int) : int =

if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program a comment (* ... *)sumTo.ml: 28 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program the name of the function being defined the keyword “let” begins a definition; keyword “rec” indicates recursion sumTo.ml: 29 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program result type int argument named n with type int sumTo.ml: 30 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program a conditional statement in OCaml sumTo.ml: 31 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program Each branch of the conditional statement constructs a result construct the result 0 construct a result using a recursive call to sumTo sumTo.ml: 32 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program print the result of calling sumTo on 8 print a new line sumTo.ml: 33 (* sum the numbers from 0 to n precondition: n must be a natural number *) let rec sumTo (n:int) : int = match n with 0 -> 0

| n -> n + sumTo (n-1)

let _ =

print_int (sumTo 8);

print_newline()

A Second OCaml Program (New Version)

Additional
commentnewSumTo.ml:

34

(* sum the numbers from 0 to n

precondition: n must be a natural number

*)

let rec sumTo (n:int) : int =

match n with

0 -> 0

| n -> n + sumTo (n-1)

let _ =

print_int (sumTo 8);

print_newline()

A Second OCaml Program (New Version)

deconstruct the value n
using pattern matching

data to be
deconstructed
appears
between
key words
“match” and
“with”

newSumTo.ml:

35

(* sum the numbers from 0 to n

precondition: n must be a natural number

*)

let rec sumTo (n:int) : int =

match n with

0 -> 0

| n -> n + sumTo (n-1)

let _ =

print_int (sumTo 8);

print_newline()

_

A Second OCaml Program

deconstructed data matches one of 2 cases:
(i) the data matches the pattern 0, or (ii) the data matches the variable pattern n

vertical bar “|” separates the alternative patterns

newSumTo.ml:

36

(* sum the numbers from 0 to n

precondition: n must be a natural number

*)

let rec sumTo (n:int) : int =

match n with

0 -> 0

| n -> n + sumTo (n-1)

let _ =

print_int (sumTo 8);

print_newline()

A Second OCaml Program

Each branch of the match statement constructs a result

as before,
construct
the result 0

as before,
construct
a result
using a
recursive
call to sumTo

newSumTo.ml:

37

OCAML BASICS:
EXPRESSIONS, VALUES, SIMPLE TYPES

38

Terminology: Expressions, Values, Types

• Expressions are computations

– 2 + 3 is a computation

• Values are the results of computations

– 5 is a value

• Types describe collections of values and the computations
that generate those values

– int is a type

– values of type int include

• 0, 1, 2, 3, …, max_int

• -1, -2, …, min_int

39

Some simple types, values, expressions

Type: Values: Expressions:

int -2, 0, 42 42 * (13 + 1)

float 3.14, -1., 2e12 (3.14 +. 12.0) *. 10e6

char ’a’, ’b’, ’&’ int_of_char ’a’

string “moo”, “cow” “moo” ^ “cow”

bool true, false if true then 3 else 4

unit () print_int 3

For more primitive types and functions over them,
see the OCaml Reference Manual here:

https://ocaml.org/releases/4.11/htmlman/libref/Stdlib.html

40

Not every expression has a value

Expression:

42 * (13 + 1) evaluates to 588

(3.14 +. 12.0) *. 10e6 ↦ 151400000.

int_of_char ’a’ ↦ 97

“moo” ^ “cow” ↦ “moocow”

if true then 3 else 4 ↦ 3

print_int 3 ↦ ()

1 + “hello” does not evaluate!

41

OCAML BASICS:
CORE EXPRESSION SYNTAX

42

Core Expression Syntax

The simplest OCaml expressions e are:

• values numbers, strings, bools, …

• id variables (x, foo, …)

• e1 op e2 operators (x+3, …)

• id e1 e2 … en function call (foo 3 42)

• let id = e1 in e2 local variable decl.

• if e1 then e2 else e3 a conditional

• (e) a parenthesized expression

• (e : t) an expression with its type

43

A note on parentheses
In most languages, arguments are parenthesized & separated by commas:

f(x,y,z) sum(3,4,5)

In OCaml, we don’t write the parentheses or the commas:

f x y z sum 3 4 5

But we do have to worry about grouping. For example,

f x y z
f x (y z)

The first one passes three arguments to f (x, y, and z)
The second passes two arguments to f (x, and the result of applying the

function y to z.)

44