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)

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

So with my recommendations above we clearly miss on parallelism, concurrency

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, concurrency

^{2}, 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 —
`None`

returning functions in python are pedagogically worse than`void`

returning 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

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

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

where

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 languagewhich 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

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

The alternative that follows from Buchberger's blackbox/whitebox principle can be analogized to

Of course this is

we may say that

In a way the iterative and the recursive approaches are two

*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 soWhiteBox | Cook from recipe |

BlackBox | Order Waiter^{3} |

*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 programming^{4}.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:

Two of the views from the other side:

In SECP

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

*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 earlier^{5}.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 SECP

^{6}Bob Harper puts into the mouth of an unnamed 'developer' the following:Noting 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?Everyone knows that algorithms as we learned them at school are irrelevant to practice

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

So students are likely to spend much of their time implementing various types of

In effect, what people call

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…

*Data Structures*spend most of their pages (and therefore student time) on the question:If the only first-class data structure I have isNow 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.pointer, how do I go about fashioning more useful data structures?

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 there

^{7}.### 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

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 orthogonalized
^{8}. - 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