Transcript Week 9 slides

CSC 580 – Theory of Programming
Languages, Spring, 2009
Week 9: Functional Languages
ML and Haskell, Dr. Dale E. Parson
ML (so-called meta-language)
(SML/NJ at http://www.smlnj.org)
• ML is a functional language.
– Side effects are possible via arrays and ref
variables, but using them is not the norm.
– No loops, normally code is free of side effects.
• Unlike Lisp, ML uses strong static typing.
– Context sensitive type inference minimizes the
amount of explicit typing in the code.
– Implicit parametric polymorphism supports
generic functions.
ML Data Types
• The usual primitive types
• Lists, tuples, and structured aggregate types
• User defined types, modules, and abstraction
interfaces for information hiding
• Immutable bindings for variables and function names
• Mutable array and ref variable types
• Strong, static, implicit type inference from context
• Nested lexical scope using let construct, closures
supported
Variable bindings are immutable
- val a = 5;
val a = 5 : int
- fun adda(x) = x + a;
val adda = fn : int -> int
- val a = 6 (* This is a totally different immutable variable! *);
val a = 6 : int
- fun adda_again(x) = x + a;
val adda_again = fn : int -> int
- adda(1);
val it = 6 : int
- adda_again(1);
val it = 7 : int
Type inference infers object types.
Type resolution occurs at compile time
- val a = 5;
val a = 5 : int
- fun adda(x) = x + a;
val adda = fn : int -> int
- adda;
val it = fn : int -> int
Implicit parametric polymorphism supports generic functions.
- fun identity(x) = x ;
val identity = fn : 'a -> 'a
- identity(4);
val it = 4 : int
- identity("foo");
val it = "foo" : string
(* Unlike Python, everything has a static type. *)
(* ‘a is a type variable, similar to a C++ template type.)
Strong, static types.
- val a = 8 ;
val a = 8 : int
- val b = 9.0 ;
val b = 9.0 : real
- a * b;
stdIn:4.1-4.6 Error: operator and operand don't agree [tycon
mismatch]
operator domain: int * int
operand:
int * real
in expression:
a*b
Strong, static types continued.
- b * a;
stdIn:1.1-1.6 Error: operator and operand don't agree [tycon
mismatch]
operator domain: real * real
operand:
real * int
in expression:
b*a
- a * floor(b);
val it = 72 : int
Strong, static typing implies.
• No variable number of function parameters.
• No eval function. What implies this concept?
• No heterogeneous lists.
• - val l = [1, 2, "a"];
• stdIn:5.9-5.20 Error: operator and operand don't agree
[literal]
• operator domain: int * int list
• operand:
int * string list
• in expression:
• 2 :: "a" :: nil
Higher Order Functions
• map, reduce and filter
• Similar to Lisp, Scheme and (later) Python
• function composition and currying
• Built into ML using “o” operator (composition) and
unparenthesized parameters (currying).
• Parenthesized parameters constitute a tuple.
• function parameter evaluation is eager
• functions are first-class objects (passed as
arguments, returned from functions)
Examples of composition, curried functions
and lambda expressions.
• ~parson/ThryLang/func/
• Function composition built into ML is more powerful
and notationally convenient than anything we (or at
least I) can define using the language. Likewise for
curried functions.
• The inability to use vararg parameters because of
strong static typing limits flexibility.
• The language constructs are powerful, but overall
flexibility and extensibility are less than with
dynamically typed languages like Python or Scheme.
Comparison to Scheme and Python
Functional Programming
• Strong type inference trades flexibility and
certain kinds of extensibility in favor of
stronger compile-time error checking.
• Perspective is compile-time verification of
program correctness. Not only are there
typically no side effects (as in pure Lisp), but
also no chance for type incompatibilities.
• Type inference minimizes explicit type
specification in the code.
Other Noteworthy Features
• PROLOG-like patterns on function variants and
data structure variants.
• Eager evaluation
fun returndiv(quotient, divisor)
= if divisor <> 0 then quotient else ~1000 ;
(* Like a C conditional statement. *)
- returndiv(8 div 2, 2);
val it = 4 : int
- returndiv(8 div 0, 0);
uncaught exception Div [divide by zero]
raised at: stdIn:5.13-5.16
Haskell
• Haskell has many features similar to ML.
• tuples, lists, structured data, modules, type inference
• Haskell is strictly pure functional programming
– no side effects
– monads hide I/O side effects behind an action abstraction
• Lazy evaluation is one of the more novel
features. Formally, normal order evaluation.
• Similar to short-circuited boolean expressions and ifthen-else control constructs in imperative languages.
• The unused expressions are never evaluated.
Lazy evaluation
• ~parson/ThryLang/func/hugsdemo.hs
returndiv quotient divisor
= if (divisor /= 0) then quotient else -1000
Main> returndiv (div 8 2) 2
4
Main> returndiv (div 8 0) 0
-1000
(div 8 0) is never evaluated unless used
It may be evaluated once, then the value is cached.
Infinite Lists are Generators
addfirsttwo (x:y:zs) = x + y
ones = 1 : ones
from n = n : from (n+1)
fromstep n m = n : fromstep (n+m) m
Main> addfirsttwo(ones)
2
Main> addfirsttwo(from 7)
15
Main> addfirsttwo(fromstep 10 10)
30
Main> addfirsttwo([ 3 .. ])
7
Main> addfirsttwo([ 3, 6 .. ])
9
Lazy Evaluation is a generalization of special purpose
mechanisms in imperative languages
• Similar to short-circuited boolean expressions and ifthen-else control constructs in imperative languages.
• Laziness allows a called function or accessed data
structure to decide when to evaluate an expression
and possibly bind its value to a parameter.
• Make the imperative special cases into a general
approach to evaluation.
• Lazy evaluation is a conditional rewrite approach.
Conclusions
• Lisp and Python are good for experimenting
with extensibility within a functional
programming framework.
• ML and Haskell are good for type-safe
functional programming with powerful builtin
mechanisms.
• Extensibility of the language itself is not well
supported in ML and Haskell.