In my last post, I gave a functional programming time line in the last 50 years.
Now I'll look at two things: The place of functional in ACM Curriculum 2013 and how C has messed up the notion of functional.
ACM Curriculum 2013
When I studied programming in the 80s we had to study bit-n-bytes-n-flowcharts. Today [page 158 of Curriculum-2013] it is:
Tier 1
[Absolute Basic – Everyone should know – 3 hours]
- Effect-free programming
- Function calls have no side effects, facilitating compositional reasoning
- Variables are immutable, preventing unexpected changes to program data by other code
- Data can be freely aliased or copied without introducing unintended effects from mutation
- Processing structured data
- e.g. Processing trees via functions with cases for each data variant
- Associated language constructs such as discriminated unions and pattern-matching over them
- Functions defined over compound data in terms of functions applied to the constituent pieces
- First-class functions
- taking, returning, and storing functions
Tier 2
[Everyone should still know – but next-level basic – 4 hours]
- Function closures
- Functions using variables in the enclosing lexical environment
- Basic meaning and definition – creating closures at run-time by capturing the environment
- Canonical idioms: call-backs, arguments to iterators, reusable code via function arguments
- Using a closure to encapsulate data in its environment
Currying and partial application
- Defining higher-order operations on aggregates
- especially map, reduce/fold, and filter
To see how important is the contribution of this latest curriculum we need…
The right perspective of function
I started my functional timeline at 1957 and Fortran. However to get a right historical perspective, we need to go back to Euler who in 1734 for the first time invoked the general notion of function and for that used the notation f(x). This notion and notation was respected and kept intact for 250 years upto and including Fortran, Pascal, even the everyone-likes-to-malign BASIC.
Until…
Until C
While C has been popularly maligned for all sorts of things – laissez faire, unsafe language etc, its general role in futzing the notion of function is not so well known.
In C, functions could be 'mathematical' functions or 'something else'…
What's that something else?
Lets try unfutz the conceptual legacy of C
In C, functions could be 'mathematical' functions or 'something else'…
What's that something else?
- Pascal called it procedure
- Fortran called it subroutine
- Basic called it proc
Lets try unfutz the conceptual legacy of C
Real and Bogus Functions? Or Real and Bogus Notions?
C made widespread the notions of function as follows:
- There are functions and there are functions
- There are programming functions and mathematical functions
- And of course they are different since programming is not mathematics
- And other such brazenly anti-intellectual bullshit
The Right Notion of function
- Of course comes from math
- It is not just syntax: f(x) = «rhs»…
- But also the key elements of semantics, viz.:
- For a relation f between A and B to be a function, two properties are required
- Many-one: (∀x∈A, y₁,y₂∈B • (x,y₁) ∈ f ∧ (x,y₂) ∈ f ⇒ y₁ = y₂ )
- Total: (∀x∈A • (Ǝy∈B • (x,y) ∈ f) )
- of which totality is somewhat flexible (such functions being called partial )
- BUT NOT MANY-ONE-NESS
- In lay language, if something returns different values depending on the phase of the moon, its not a function even if it looks/walks/quacks like one.
- For the syntactic convenience of the mathematical idiom
f(x,y,…) = «rhs»
to make sense, be useful and not be as clear as mud, it is key that the two locutions
f(x,y,…) and «rhs»
be interchangeable
(perhaps modulo secondary considerations like performance, readability etc)
usually called by the bombastic term…
Referential Transparency
Of course by now we know that most – so called imperative – languages
violate this.
And if they do it is all the more imperative(!!) that students being taught with these be given a – probably different – referentially transparent ontology to think with than they program in(to).
A classical mathematician looking upon the so-called functions in most programming languages wherein it is quite normal for f(x) ≠ f(x) 1 would perhaps just blink and say
This definition of function is ill-defined
What is…
And if they do it is all the more imperative(!!) that students being taught with these be given a – probably different – referentially transparent ontology to think with than they program in(to).
A classical mathematician looking upon the so-called functions in most programming languages wherein it is quite normal for f(x) ≠ f(x) 1 would perhaps just blink and say
This definition of function is ill-defined
What is…
Implicit FP in Curriculum 2013
is at least as important, maybe more so, than what is explicitly said.
Let's try spell it out.
Let's try spell it out.
- Studying functional programming does not necessarily imply studying a functional language [Of course no stops one from doing so]
- Functional programming is not a subject but a core set of topics needing from 3 to 7 contact hours
- While language-wars may amuse people with a lot of arm-chair time, the juxtaposition and cross-linkage of imperative and functional styles should be taken as complementary rather than competitive [My 20 year-old syllabus]
- Most significantly, in Curriculum-2013 FP and OOP are juxtaposed. It is important to deconstruct the significance of this:
1 There is NO UNIVERSAL LANGUAGE
no single notation/language would do full justice to the full gamut of CS.
Peter Naur noted in [@@] that Algol-60 had the goal of being a universal algorithmic language. 25 years later and wiser he considers this view wrong-headed – there is not and cannot be any such language. A view that also directly follows from Gödel's theorem. But what does Gödel's theorem have to do with CS?!
So with my recommendations above we clearly miss on parallelism, concurrency2, event-driven architecture and much else.
One of the things that follows from the Rob Hagan quote I started timeline with
Important not to misunderstand this as a pro-scheme stand
Peter Naur noted in [@@] that Algol-60 had the goal of being a universal algorithmic language. 25 years later and wiser he considers this view wrong-headed – there is not and cannot be any such language. A view that also directly follows from Gödel's theorem. But what does Gödel's theorem have to do with CS?!
So with my recommendations above we clearly miss on parallelism, concurrency2, event-driven architecture and much else.
One of the things that follows from the Rob Hagan quote I started timeline with
Important not to misunderstand this as a pro-scheme stand
2 Education needs to be more pro-concept less pro-fashion
- Scheme exemplars CS concepts elegantly
- C implements them efficiently once understood but exemplifies them badly when not
- Python is a mixed bag —
Nonereturning functions in python are pedagogically worse thanvoidreturning in C. However once a programmer has picked up clear, well-defined conceptual division of procedure/function (probably from other languages), python's first-classness makes easy to slide from mostly-functional programming to fully object-oriented.
Helium for the conceptual clarity, Python for 'getting real'. And until I get Helium up, I guess its going to be some mishmash of gofer+ghc.
In retrospect I can say that when a dual-language approach is used more understanding follows from wrestling with the impedance-mismatch between the two than any one alone can give.
This is related to something that was quite widely known and understood in the 80s but got lost in the 90s and after…
3 Pascal is a good language to teach programming
because
Related to the shift from the 1970-80s model of clearly separated teaching languages and real-world languages to the widespread use of today's…
- Pascal has a proper pair of fundamental-concepts: procedure and function
So did Fortran and Basic but then they did not have the other pluses of Pascal… - A good set of type abstractions
Related to the shift from the 1970-80s model of clearly separated teaching languages and real-world languages to the widespread use of today's…
4 Omnibus kitchen-sink languages
Many people seem to think that MIT is retrogressive in replacing scheme by python for its intro-to-programming course… Right for the wrong reasons?? And others are might pleased.
In 1980s MIT used a Lisp tailor-made for education viz. scheme, to introduce programming. Today it uses vanilla-python. Maybe more than the Lisp→Python that is the retrogression its the the tailor-made to ready-made.
Brings me to a central tenet of pedagogy:
In 1980s MIT used a Lisp tailor-made for education viz. scheme, to introduce programming. Today it uses vanilla-python. Maybe more than the Lisp→Python that is the retrogression its the the tailor-made to ready-made.
Brings me to a central tenet of pedagogy:
5 Teaching Order
Every even beginning teacher gets that these three
As example consider teaching/learning English. The Oxford English Dictionary contains all of English. And so to teach English, the due diligence that a teacher can do is to throw the OED at the beginner… Right?
Teachers of programming who throw real-world omnibus languages at beginners without calibrating the learning-curve are doing about the same.
Ironically in the teaching of natural language, we have progressed in the last 100 years from an over-emphasis on early spelling and grammar – formal structure – to the idea that simple usage should precede formal understanding.
In the case of programming-education we have regressed from separated teaching and real-world languages to omnibus languages.
Its so salutary for the health to have a tonne of bricks over one's head, aint it? [As long as we are the unloader and not the receiver!]
Curriculum 2013 by making Blooms taxonomy centerstage and simplifying 6 to 3 levels has done a signal service to CS.
Hopefully, curriculum-2013 will have the effect that the now-forgotten metric f/l
where f = subset of language features learnable/teachable in first course
l = size of full language
which was implicitly understood in the 70s and 80s when Pascal was at its heyday will again be revived for programming pedagogy.
What we now need is, in analogy to courses that fail students…
- Knowledge
- Learning
- The learning-curve
- Distance
- Velocity
- Acceleration
As example consider teaching/learning English. The Oxford English Dictionary contains all of English. And so to teach English, the due diligence that a teacher can do is to throw the OED at the beginner… Right?
Teachers of programming who throw real-world omnibus languages at beginners without calibrating the learning-curve are doing about the same.
Ironically in the teaching of natural language, we have progressed in the last 100 years from an over-emphasis on early spelling and grammar – formal structure – to the idea that simple usage should precede formal understanding.
In the case of programming-education we have regressed from separated teaching and real-world languages to omnibus languages.
Its so salutary for the health to have a tonne of bricks over one's head, aint it? [As long as we are the unloader and not the receiver!]
Curriculum 2013 by making Blooms taxonomy centerstage and simplifying 6 to 3 levels has done a signal service to CS.
Hopefully, curriculum-2013 will have the effect that the now-forgotten metric f/l
where f = subset of language features learnable/teachable in first course
l = size of full language
which was implicitly understood in the 70s and 80s when Pascal was at its heyday will again be revived for programming pedagogy.
What we now need is, in analogy to courses that fail students…
6 A system that fails courses
Two 'real-world' example-courses that recently came to my notice will illustrate the kind of courses that need to be failed
- End-sem C++ exam has question: List 10 keywords of C++
- [Student reports]: We learnt Lisp, Perl, Mathlab (and a couple others) in 2 classes. 'Learning' meant writing factorial in each of these [in the notebook not on computer]
7 Lost Knowledge
Pascal, Fortran and even the everyone-likes-to-malign Basic
got something right that most subsequent languages goofed on – a
programming language needs to have both procedural and functional
abstraction because
8 Declaration and Imperation need to be equally emphasized
Note the title-bar of this blog!!
Or equivalently
Or equivalently
9 Values and Effects are equally fundamental to programming
Functional programming has remained an academic ivory-tower for so long
because there were not enough Rob Hagan's to transfer the clarity of scheme to the reality of Cobol.
ACM Curriculum 2013's putting FP as absolute basic concepts but deemphasizing the specific language should begin to correct this
ACM Curriculum 2013's putting FP as absolute basic concepts but deemphasizing the specific language should begin to correct this
10 Abstract vs Concrete Data Structures
One of the biggest fanfares in the OOP world is that abstract data (ADTs) is the best thing since sliced bread. Abstract hot air may be the more apposite description.
Conversely one of the biggest quiet successes of FP is concrete data strucures. If all one's data structures could be as easy (concrete) as numbers wouldn't it be utopia? Every modern language that has a list-literal syntax like
Conversely one of the biggest quiet successes of FP is concrete data strucures. If all one's data structures could be as easy (concrete) as numbers wouldn't it be utopia? Every modern language that has a list-literal syntax like
[1,2,3] subscribes to this and this comes from FP (Lisp).
11 Recipe-Model vs Blackbox-Whitebox Principle
Knuth onwards, a dominant model for the question What is programming? is the 'recipe model.'
This inevitably follows from seeing imperative programming as being THE way of programming.
The alternative that follows from Buchberger's blackbox/whitebox principle can be analogized to If the waiter can be ordered why bother to cook from a recipe?
Of course this is not a rhetorical question – there may be many good reasons to cook. And so
we may say that recursively drill down from blackbox view to whitebox view is the methodological counterpart of FP just as the iteratively following a recipe is the counterpart of imperative programming4.
In a way the iterative and the recursive approaches are two fundamental approaches to problem solving and is related to…
The alternative that follows from Buchberger's blackbox/whitebox principle can be analogized to If the waiter can be ordered why bother to cook from a recipe?
Of course this is not a rhetorical question – there may be many good reasons to cook. And so
| WhiteBox | Cook from recipe |
| BlackBox | Order Waiter3 |
In a way the iterative and the recursive approaches are two fundamental approaches to problem solving and is related to…
12 Algebraic and Algorithmic viewpoints
It will not be too much of a surprise to say that the primary proponent of the philosophy: programming is implementing algorithms is the great Donald. E. Knuth. And it is perhaps the very stature of Knuth that has prevented the complementary view: programming is implementing algebra from becoming popular earlier5.
Two of the views from the other side:
In SECP6 Bob Harper puts into the mouth of an unnamed 'developer' the following:
In the programming syllabus I made 20 years ago, there was this table:
The last 60 years of programming pedagogy being dominated by imperative programming has resulted in missing the wood – algebra – for the trees – algorithm. We may hope the reinstatement of FP as core-CS will redress this imbalance of overfocussing
Two of the views from the other side:
- SICP talks of scheme as supporting procedural epistemology
- Iverson talks of APL as imperative mathematics [cant find reference]
In SECP6 Bob Harper puts into the mouth of an unnamed 'developer' the following:
Everyone knows that algorithms as we learned them at school are irrelevant to practiceNoting that he is careful to stay one remove away from the blasphemy (and I two!). Perhaps the relevance of algorithms will be restored by balancing the algorithmic with the algebraic viewpoints?
In the programming syllabus I made 20 years ago, there was this table:
| Algebra | Algorithm | |
|---|---|---|
| Worlds | The Timeless World | World of Time |
| Domain | Mathematics | Programming |
| Syntax | Expressions | Statements |
| Semantics | Values | Objects |
| Explicit | Data Structures | Control Structure |
| Think with | Input-Output relations | State Change |
| Abstraction | Function | Procedure |
| Relation | Denote programs ⇒ | ⇐ Implement function |
13 The How over the What
The following table is a commonplace
and so we need not spend more time on it.
I would rather focus on a related area that happens to be quite neglected – filling up these question-marks:
| Paradigm | Methodological | Programming |
|---|---|---|
| How-oriented | Imperative | |
| What-oriented | Functional (declarative) |
I would rather focus on a related area that happens to be quite neglected – filling up these question-marks:
| Code | Data | |
|---|---|---|
| How-over-what | Imperative | ? |
| What-over-how | Functional |
14 Data Dependency
From the mundane through the arcane, imperative programmers have so much excessive spurious data-dependency they do not even notice it. Now if we deconstruct FP and remove from it all the vague moralistic feel-good about being mathematical, the whole issue boils to
- being explicit about dependencies... results in
- minimizing them
The Essence of Functional Programming behind all the monadology is just being explicit about data dependencies.
Consider as example the following C and python fragments to interchange variables x and y.C:
t = x;
x = y;
y = t;
Python
x, y = y, x
That the first has 6 sequencing points and one spurious variable as compared to the second is perhaps the lesser problem compared to the fact that dyed-in-the-wool imperative programmers think it completely natural to write the first.
Hopefully programmers fed on mothers-milk of Curriculum 2013 will begin to make the new generation of programmers more conscious of data dependency.
15 Distinguishing data and storage structures
Most textbooks that claim to be on Data Structures spend most of their pages (and therefore student time) on the question:
So students are likely to spend much of their time implementing various types of linked-lists and thereby miss out the more fundamental question on when one should use a list, when a set, when a bag (multi-set).
In effect, what people call data-structures is usually storage-structures (in half-assed languages like C).
Since my 1991 Travails of teaching C seems to be getting popular of late with people wanting to make a case for functional and against imperative/OO programming, fairness demands me to say something…
If the only first-class data structure I have is pointer, how do I go about fashioning more useful data structures?Now while this may be a useful line if the only language we have is a low-level one such as C, in the programming world of 2015, such a line is less and less fruitful.
So students are likely to spend much of their time implementing various types of linked-lists and thereby miss out the more fundamental question on when one should use a list, when a set, when a bag (multi-set).
In effect, what people call data-structures is usually storage-structures (in half-assed languages like C).
Since my 1991 Travails of teaching C seems to be getting popular of late with people wanting to make a case for functional and against imperative/OO programming, fairness demands me to say something…
In defence of C
I bashed C too much there7.
C is laissez faire on all fronts
…pointers, structured programming, inline asm, you name it. People who
think CS can be taught via C are the idiots, not the inventors of C.
Actually C just continued and complemented the tradition of…
Lisp/APL were the first to futz the notion of procedure
both of which syntactically have only 'functions' but which allow 'overloading' them to be procedures.
IOW as Ive tried to say repeatedly, C is not a bad language to program with.
It is however unpleasant to teach and its criminal if its all a teacher hands out to students to think with
Better late than never, the new status of FP in Curriculum 2013, should begin to correct
IOW as Ive tried to say repeatedly, C is not a bad language to program with.
It is however unpleasant to teach and its criminal if its all a teacher hands out to students to think with
Better late than never, the new status of FP in Curriculum 2013, should begin to correct
Fifty years of Misunderstandings around Programming
such as
- FP is academic and ivory-towerish
- Functional ≡ Unrealistic
- Studying Functional Programming is a lifetime's project
- FPLs are inefficient
- Programming is not math
- FP is not so much about programming-languages but about the thinking language
- FP is about as academic to CS as abc is to literacy
- A well-rounded CS-education, is incomplete without a minimum of 4 hours of FP contact. More than 7 hours is not strictly required in the core-curriculum.
- Inefficiency is irrelevant once thinking and programming languages have been orthogonalized8.
- From Euclid, Al-Khwarizmi and Bhaskara down to the mid 19th century, mathematicians would have been amused at the claim that math and computing were different/disparate fields. Maybe future generations will see computing as the medicine that cools the delirium of Cantor?
Acknowledgements
People who record history also happen to be part of it.
Various remarkable people and interesting circumstances, have conduced to make my connection with programming and functional programming in particular.
I guess I need to ack these… in a separate post
Followup
Primacy is a view seemingly from the other side (or at least complementary) to this post
Footnotes:
1 Of course in most cases it is not a case of f(x) ≠ f(x) but
f(x) != f(x) because most programming languages have != not ≠. Some
will call this hair-splitting. Programming language experts would of
course recognize these as central questions of semantics — separation
and interaction of object and meta languages.
2 They are different! See: parallelism-is-not-concurrency and parallelism-and-concurrency-revisited
and most famously Rob Pike
3 Or parent?
4 And CS 2013 by internalizing Bloom's taxonomy into the sequence – familirize → use → evaluate/judge, may be said to meta-circularly use the FP/recursive formulation
5 That these two words meet in their point of origin is piquant.
Al-Khwarizmi after whom we get 'algorithm' wrote the book Al-Gabr after which we get 'algebra'.
6 Hamming-distance of 1 from SICP not coincidental
7 If Backus can revise his position after 20 years, hopefully so can I
:-)
8 More precisely Orthogonalizing programming and thinking language also orthogonalizes program and programmer efficiencies
No comments:
Post a Comment