Search This Blog


Friday, July 31, 2015

Faith and Rats, Gödel and Computer Science

Computer scientists dismiss Gödel as mathematics
Mathematicians classify Gödel as logic
Logicians slot Gödel into meta-mathematics
Meta-mathematicians know the truth of the matter…
…and have been dead for a century

I would like to suggest that this misunderstanding (or rather non-understanding) does not make it non-true.¹ Many educated people do know that Gödel’s theorem(s) is important even portentous. But somehow – like war – Yeah its bad but not my problem.

Let’s use the services of
A fever is raging in the town.
People are dying.

And I happen to find…
In the closet…
A dead rat

“What do rats have to do with…”

The Plague?

Do we need to start having a fever and swelling in the armpits to change our minds?
To my mind the mathematicians and CSists who think of Gödel as irrelevant are like people with a dead rat in their closet who are now beginning to run a fever and who still keep insisting:
“Whats a dead rat to do with the plague? Why should I bother?”
Gödel’s theorem is a dead rat in plague infested town. In the 1930s, people understood this. Somehow now everyone has forgotten. This post is to remind of these well-known and more well-forgotten facts.

The Terrible Theorem

Starting with the cute paradoxical statement

This statement is false

which is true if its false and false if true,  Gödels theorem maps out the large gulf between what is provable and what is true.
Now on the face of it this seems like a ridiculous thing to make a song-n-dance about. Surely there are truths that we dont know (yet)? What of it? Then science studies better... Then some more truths are revealed... etc...

To understand why its a big deal we need to understand the difference between

Analytic and Synthetic Truths

Monday, June 15, 2015

Richard O'Keefe's responses to FP Timeline

Richard O'Keefe of Otago whose quote I started FP Timeline with, wrote me some rather detailed comments about history which have interesting titbits of info.

Tuesday, June 9, 2015

Functional Programming: A Moving Target

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

Wednesday, April 29, 2015

Functional Programming: A Timeline

Rob Hagan at Monash had shown that you could teach students more Cobol with one semester of Scheme and one semester of Cobol than you could with three semesters of Cobol.
Richard O'Keefe on Erlang list
Well that was before Functional Programming became such a buzzword.
These days FP is quite a buzzword. Is this for good or bad?
If real worldgood well then Scala and Clojure and Erlang and Haskell becoming more and more 'real world' is a wonderful thing.
If what is good is understanding then I am not so sure. Many things about programming, pedagogy and programming-pedagogy that were widely understood in the 1970s and 80s have mysteriously become un-understood today.
However in this darkening of the age there are some glimmers… eg ACM's 2013 curriculum.
In this post I would like to delineate a timeline of the semantics and significance of Functional in the last 50 years. In subsequent posts I'll try to deconstruct how the semantics has shifted around in this time.


The first programming language – Fortran
The first functional programming language – For(mula)Tran(slator)

Why? Whoa! How?

Read on…

Tuesday, April 21, 2015

Between Poverty and Universality lies Structure

Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself           —  Eric Raymond

In ancient times people set each other puzzles such as:

       Can God make a stone so heavy that he can't lift it?

These puzzles-of-omnipotence can be rephrased in theory-of-computation lingo:

       Can God compute the uncomputable?
       If he can, how is it uncomputable?
       If he cant, how is he God?

So what are those limits of/by structure?  Unsurprisingly related to God-el's theorem:
God-el's Theorem says that for any record player, there are records which it cannot play because they will cause it to self-destruct

And like record players what about programming languages whose abstractions can be arranged to break the language?

Structure is good because it reduces breakage; its bad because it imprisons us into precooked forms.

Following I explore the space between poverty and universality; a space which for want of a better word I will simply call structure, the most elusive being the structure of syntax.

Thursday, March 26, 2015

CS History 0

Are real numbers real?

Wait!! What does this have to do with programming? Or even computer science??

Sounds like angels-on-the-head-of-a-pin philosophy No??
NO!  CS came into existence because of this question!

Monday, March 2, 2015

Unicode: Universal or Whimsical?

Unicode Classification

In my last post, I wrote about two sides to unicode — a universal side and a babel side. Some readers while agreeing with this classification were jarred by a passing reference to ‘gibberish’ in unicode⁵.

Since I learnt some things from those comments, this post expands that classification into these¹.
  1. Babel
  2. Universal
  3. Legacy
  4. Unavoidable mess
  5. Political mess
  6. Whimsical

Thursday, February 26, 2015

Universal Unicode

What is the 'uni-' in unicode? According to the official records it comes from Unique Uniform and Universal.

Unicode starts out with the realization that ASCII is ridiculously restrictive, or the world is larger than the two sides of the Atlantic¹. This gives rise to all the blocks from Arabic to Zhuang.

However the greatest promise of unicode lies not in catering to this tower of babel but rather in those areas that are more universal. Yeah I know technically this distinction between universal and international will not stand up to scrutiny.

Tuesday, January 6, 2015

Unicode and the Universe

If you're trilingual you speak three languages, if you're bilingual you speak two languages, if you're monolingual you're American.

Mark Harris on the python list
Well if one reads that thread above, one would find that people were rather uptight with Mark Harris for that statement. And yet they have the same insular attitude towards ASCII-in-programming that Mark describes in Americans towards English (or more correctly Americanese); to wit they consider that programming with ASCII (alone) is natural, easy, convenient, obvious, universal, inevitable etc.

Is it mere coincidence that the 'A' of ASCII is short for American?

Friday, September 26, 2014


In the early 90s  I used gofer to teach FP in the introductory programming class at the university of Pune.  At first I used Miranda/Scheme, then gofer. I was also impressed with Dijkstra's philosophy of making function application explicit with a dot ('.') and decided to incorporate this into gofer.  This changed gofer was called pugofer.

The philosophy of these changes is here. Summary of changes is:

Tuesday, August 12, 2014

Universities starting with functional programming

Here's a list of some universities that are using functional languages to teach programming. As I find more data, it will be added. So please let me know (with links!!) what Ive missed – lists are particularly welcome, but individual universities is also welcome.  Also other languages that have some claim to being functional.
Haskell – official list (list)
At quora (also scheme and ML dialects) 
Carnegie Mellon 

Wednesday, July 9, 2014

ACM FDP – Invited Talk

I was an invited speaker at the ACM faculty development program (FDP) organized jointly by ACM and VIT Pune on 9th July 2014.
The stuff of my talk — and good deal of other stuff that I did not manage to cover for lack of time :D — is put up at github.

To view, you will need

Tuesday, May 13, 2014

Unicode in Haskell Source

After writing Unicoded Python, I discovered that Haskell can do some of this already.  No its not even half way there but I am still mighty pleased!

Tuesday, April 29, 2014

Unicode and the Unix Assumption

Once upon a time, file was a rich, profound, daunting and wondrously messy concept. It involved ideas like
  • record orientation
  • blocking factor
  • partitioned data sets
and other wonders of computer (rocket) science.

Then there came along 2 upstarts, playing around in their spare time with a machine that their Lab had junked. They were having a lot of fun…

They decided that for them File was just List of Bytes.
type File = [Byte]
Oh the fun of it!

Saturday, April 19, 2014

Unicode in Python

1 Introduction

Python has been making long strides in embracing unicode. With python 3 we are at a stage where python programs can support unicode well however python program-source is still completely drawn from the ASCII subset of unicode.
Well… Actually with python 3 (not 2) this is already possible
def solvequadratic(a,b,c):
    Δ = b*b - 4*a*c
    α = (-b + sqrt(Δ))/(2*a)
    β = (-b - sqrt(Δ))/(2*a)
    return (α, β)

>>> solvequadratic(1,-5,6)
(3.0, 2.0)
Now to move ahead!