I am often surprised that people think of recursion solely confined to the narrow context of recursive functions, missing the widespread and ubiquitous status of recursion in computer science. If I may be permitted some jargon, we need to move on from recursion in recursive functions to
[2] I always have a hell of a time explaining to students that a classic C linked-list is recursive data just as the classic factorial is recursive code.
In fact the C data structure is more recursive than the equivalent Haskell. In haskell:
data List t = Cons t (List t) | Empty
In C:
struct node
{
t elem;
struct node *next;
};
We now rewrite this by opening it up into two types – the node type and the pointer type:
typedef struct node *nodeptr;
struct node
{
t elem;
nodeptr next;
};
So: node contains nodeptr and nodeptr points to node — mutual recursion. In comparison, in Haskell there is only single/direct recursion – the definition of List t contains a reference to List t
Now embed this in an app where there are say a dozen different kinds of lists. What happens? In C each of those different lists is manifest as a mutually recursive data structure, ie 12 pairs of mutual recursion. In Haskell, we see only [t] for each of the different element-t types. ie the polymorphism of the haskell type reduces the 24 C-recursions to become the single one, bundled into the system.
In all fairness most modern languages (except go?) are closer to the FP paradigm than to C. Though the FP model has the edge — if one wishes to explicate each/any of those types one can to so, if not the system takes care of it correctly.
In short, as we become more civilized, type-inference is moving from the luxury to the necessity class.
The Recursion Design Pattern
which has a large number of instances such as- Loops [1]
- Recurrence relations
- Recursive functions
- Recursive data – eg linked lists, trees[2]
- Nesting – expressions, code, file-hierarchies, XML , S-expressions…
- Self reference – Y combinator
- Well founded induction
- Structural induction
- Bootstrapping
- Language to describe language – syntax – yacc in yacc
- Language to describe language – semantics – lisp in lisp – metacircularity
- Language to describe language – Pitfalls — the language of regular expressions cannot be specified as a regular language
- Gödel's theorem ← meta-mathematics ← ordinary math
- Undecidability ← universal TM ← Turing machine as ordinary compute-er
- Reentrancy
[An OS-like program fails to be reentrant for the same reason that a Fortan-like language fails to support recursion – non use of stack]
- Virtualization in OS
- Introspection in modern languages
- Models to metamodels
- Corecursion
- laziness, infinite datastructures
- semantics of generators/iterators in languages like python - von Neuman machine
- code is data – quondam hardware becomes software
- data can be code – viruses - Self-modifying code
Footnotes
[1] Many programmers find it hard to understand (believe?) that loops and recursion are equivalent[2] I always have a hell of a time explaining to students that a classic C linked-list is recursive data just as the classic factorial is recursive code.
In fact the C data structure is more recursive than the equivalent Haskell. In haskell:
data List t = Cons t (List t) | Empty
In C:
struct node
{
t elem;
struct node *next;
};
We now rewrite this by opening it up into two types – the node type and the pointer type:
typedef struct node *nodeptr;
struct node
{
t elem;
nodeptr next;
};
So: node contains nodeptr and nodeptr points to node — mutual recursion. In comparison, in Haskell there is only single/direct recursion – the definition of List t contains a reference to List t
Now embed this in an app where there are say a dozen different kinds of lists. What happens? In C each of those different lists is manifest as a mutually recursive data structure, ie 12 pairs of mutual recursion. In Haskell, we see only [t] for each of the different element-t types. ie the polymorphism of the haskell type reduces the 24 C-recursions to become the single one, bundled into the system.
In all fairness most modern languages (except go?) are closer to the FP paradigm than to C. Though the FP model has the edge — if one wishes to explicate each/any of those types one can to so, if not the system takes care of it correctly.
In short, as we become more civilized, type-inference is moving from the luxury to the necessity class.
No comments:
Post a Comment