Python from Wise Guy's Viewpoint

[Neelakantan Krishnaswami]

In article <0Izmb.25575$Fm2.12537 at attbi_s04>, Marshall Spight wrote:
><prunesquallor at comcast.net> wrote in message news:ismdcj0d.fsf at comcast.net...
>>
>> Are they happy with something like this?
>>
>> (defun black-hole (x)
>>   #'black-hole)
>>
>> (for non lispers, the funny #' is a namespace operator.
>>  The black-hole function gobbles an argument and returns
>>  the black-hole function.)
> 
> Ha!
> 
> Although this doesn't get me any closer to my goal of simple,
> useful, correct program that cannot be proven typesafe. I don't
> believe the feature this function illustrates could be useful; you
> have to have a handle on black-hole before you can invoke it, so
> getting it back as a return value doesn't get me anything.  But it's
> a nice example.

The feature this program demonstrates is useful! It's a function of
recursive type; in Ocaml (invoked with the -rectypes option) it would
type as:

  # let rec blackhole x = blackhole;;
  val blackhole : 'b -> 'a as 'a

With a little bit more work, you can use recursive types to represent
(for example) infinite streams:

  type 'a stream = unit -> 'a * 'b as 'b

  let head stream = fst(stream())
  let tail stream = snd(stream())
  let cons h t = fun() -> h, t

  let rec unfold head tail cons seed =
    let rec f() =
      let h = head seed in
      let t = tail seed in
      cons h (unfold head tail cons t)
    in f

So now you can write the infinite stream of ones as

  let id x = x

  let ones = unfold id id cons 1

and the natural numbers as

  let nats = unfold id ((+) 1) 0 cons

You can write a function that gives you every even or odd element of a
stream as:

  let ($) f g x = g(f x)

  let evens s = unfold head (tail $ tail) cons s
  
  let odds s = unfold head (tail $ tail) cons (tail s) 


-- 
Neel Krishnaswami
neelk at cs.cmu.edu