Levels of Achievements
Levels of achievements in this course:
Lowest: “I learned some programming languages.” Principles of Programming Languages
1/11
Levels of Achievements
Levels of achievements in this course:
Lowest: “I learned some programming languages.”
Principles of Programming Languages
Medium: “I learned some topics in programming languages.” Principles of Programming Languages
1/11
Levels of Achievements
Levels of achievements in this course:
Lowest: “I learned some programming languages.”
Principles of Programming Languages
Medium: “I learned some topics in programming languages.”
Principles of Programming Languages
Highest: “I began to see through the features in programming
languages.”
Deconstruction/Reductionism of Programming Languages?
1/11
Why This Course Exists
“You can pick up another language easily. It’s just another syntax.”
Was true 50 years ago because most languages had been just superficial enhancements to the von Neumann model:
1 word memory ←→ CPU
i.e., still limited by s := s + a[i].
This is why they failed at abstraction, modularity, reusable
components. (Even many OO languages today.)
(From John Backus’s Can programming be liberated from the von
Neumann style? (1977).)
So people (including Backus) made new languages to explore new models. Therefore unfortunately for you. . .
2/11
Why This Course Exists
“You can pick up another language easily. It’s just another syntax.” Now obsolete and false, even for practical programming languages.
You have experienced all three of Python, C, and Java. Some of you Javascript too or will soon.
Did the 1st one help you pick up the 2nd one? The 3rd one? If you have code already written in one, do you have confidence in translating it into another, or would you rather rewrite from scratch?
(This is a good time for you to relate your experience!) Because their differences are semantic—in [mental] models.
3/11
Course Overview
Part I:
Haskell. (Not comprehensive—I do the hard parts and some live-coding; you learn the easy parts.)
Some topics stemming from it.
4/11
Course Overview
Part I:
Haskell. (Not comprehensive—I do the hard parts and some live-coding; you learn the easy parts.)
Some topics stemming from it.
Part II:
Syntax: Moar context-free grammars; simple parsers.
Semantics: By implementing toy languages in Haskell.
Why in Haskell: Almost like math definition, and executable. And this is just an undergrad course.
(In a grad course I would do the actual pure math.)
Next few slides elaborate a bit. . .
4/11
Example Topic: Evaluation Order
Define f(x) = 4. Now f(1/0) =?
Call by value (most languages): Evaluate 1/0 first. Error.
Lazy evaluation (e.g., Haskell): Don’t evaluate 1/0 yet, just plug in as-is. Oh x is unused, f (1/0) = 4.
5/11
Example Topic: Evaluation Order
Define f(x) = 4. Now f(1/0) =?
Call by value (most languages): Evaluate 1/0 first. Error.
Lazy evaluation (e.g., Haskell): Don’t evaluate 1/0 yet, just plug in as-is. Oh x is unused, f (1/0) = 4.
Consequence: In Haskell many short-circuiting operators and control constructs are user-definable; in other languages you’re stuck with what’s hardwired.
5/11
Example Topic: Evaluation Order
Define f(x) = 4. Now f(1/0) =?
Call by value (most languages): Evaluate 1/0 first. Error.
Lazy evaluation (e.g., Haskell): Don’t evaluate 1/0 yet, just plug in as-is. Oh x is unused, f (1/0) = 4.
Consequence: In Haskell many short-circuiting operators and control constructs are user-definable; in other languages you’re stuck with what’s hardwired.
Aside: Scheme is call by value, but provides a macro system for user-definable control constructs and other constructs.
5/11
Example Topic: Parametric Polymorphism
In Haskell define: trio x = [x, x, x] [Inferred] Type: t -> [t]
Like Java’s
trio 0 and trio “hello” are both legal.
6/11
Example Topic: Parametric Polymorphism
In Haskell define: trio x = [x, x, x] [Inferred] Type: t -> [t]
Like Java’s
trio 0 and trio “hello” are both legal.
User chooses what type to use for the type variable t, and
implementation not told what it is.
Consequence: Behaviour cannot vary by types. Corollary: Inflexible, but easy to test—test on one type and conclude for all types.
6/11
Example Topic: Parametric Polymorphism
In Haskell define: trio x = [x, x, x] [Inferred] Type: t -> [t]
Like Java’s
trio 0 and trio “hello” are both legal.
User chooses what type to use for the type variable t, and
implementation not told what it is.
Consequence: Behaviour cannot vary by types. Corollary: Inflexible, but easy to test—test on one type and conclude for all types.
Teaser preview: Haskell allows type-determined behaviour, but the function type will look like Foo a => a -> [a]
6/11
Some Other Example Topics
Mutable variables.
If there is time: Continuations.
If there is time: Logic programming.
7/11
Practicality
My presentation of languages will tend to be academic.
This is not because they are impractical. It is only because I am teaching, not training, and I am teaching ideas.
Example: I use singly-linked lists all the time, but random-access arrays and efficient dictionaries are available in the standard libraries.
But we will have a guest talk by some functional programming practitioners (they’re using Clojure).
8/11
Appendix: Backus’s Proposal
Backus’s proposal:
Higher order functions that work on aggregates (a whole list or array or dictionary or. . . )
Combining forms e.g., function composition (g ◦ f ).
Reasoning by algebra.
If you need state, have coarse-grained state transitions
stateless function that does a lot
old state
answer new state
rather than changing only one word at a time. These became the tenets of functional programming.
9/11
Higher-order Functions on Aggregates
(Notation: To apply a function to several parameters: Haskell:f x y z Scheme:(f x y z) )
10/11
Higher-order Functions on Aggregates
(Notation: To apply a function to several parameters: Haskell:f x y z Scheme:(f x y z) )
map f [x0, x1, …] computes [f x0, f x1, …] map abs [3, -1, 4] computes [3, 1, 4] Scheme: (map abs ’(3 -1 4))
10/11
Higher-order Functions on Aggregates
(Notation: To apply a function to several parameters: Haskell:f x y z Scheme:(f x y z) )
map f [x0, x1, …] computes [f x0, f x1, …] map abs [3, -1, 4] computes [3, 1, 4] Scheme: (map abs ’(3 -1 4))
foldr (+) 0 [3, 1, 4] computes 3+(1+(4+0)) Scheme (using Racket): (foldr + 0 ’(3 1 4))
10/11
Higher-order Functions on Aggregates
(Notation: To apply a function to several parameters: Haskell:f x y z Scheme:(f x y z) )
map f [x0, x1, …] computes [f x0, f x1, …] map abs [3, -1, 4] computes [3, 1, 4] Scheme: (map abs ’(3 -1 4))
foldr (+) 0 [3, 1, 4] computes 3+(1+(4+0)) Scheme (using Racket): (foldr + 0 ’(3 1 4))
“On aggregates”: Work on a whole list at once (or array, or some “container”. . . )
10/11
Higher-order Functions on Aggregates
(Notation: To apply a function to several parameters: Haskell:f x y z Scheme:(f x y z) )
map f [x0, x1, …] computes [f x0, f x1, …] map abs [3, -1, 4] computes [3, 1, 4] Scheme: (map abs ’(3 -1 4))
foldr (+) 0 [3, 1, 4] computes 3+(1+(4+0)) Scheme (using Racket): (foldr + 0 ’(3 1 4))
“On aggregates”: Work on a whole list at once (or array, or some “container”. . . )
“Higher-order function”: Some parameters are functions—customizable.
10/11
Combining Forms
Obvious example: Function composition (g ◦ f ).
Haskell: g . f Racket: (compose g f)
foldr (+) 0 . fmap abs computes the 1-norm of your vector. (Unfortunately the equivalent Scheme code is not as nice.)
11/11
Combining Forms
Obvious example: Function composition (g ◦ f ).
Haskell: g . f Racket: (compose g f)
foldr (+) 0 . fmap abs computes the 1-norm of your vector. (Unfortunately the equivalent Scheme code is not as nice.)
There are other combining forms. Here is an example in Haskell: f &&& g satisfies: (f &&& g) x = (f x, g x)
11/11
Combining Forms
Obvious example: Function composition (g ◦ f ).
Haskell: g . f Racket: (compose g f)
foldr (+) 0 . fmap abs computes the 1-norm of your vector.
(Unfortunately the equivalent Scheme code is not as nice.)
There are other combining forms. Here is an example in Haskell: f &&& g satisfies: (f &&& g) x = (f x, g x)
The point:
You’ve got functions that perform basic tasks on aggregates. Now hook them up to perform compound tasks.
This is not about shorter code (although it has that side effect). This is about working with building blocks.
11/11