University of Cincinnati Logo

CS-4003 - Organization of Programming Languages
Electrical Engineering and Computer Science

Notes Contributed by Students
    Amber Watripont and Kevin Ernst
        question: Why are 'virtual' functions called virtual when, in fact, they are really there?
        answer: Amber located a link and from there I located a pretty good discussion on the subject. Here it is.
    Kevin Ernst
        question: In Scheme, is building a list in continuation passing style much slower than just finding, say, the last element in the list?
        answer: It's incredibly slower if you use append but not if you use cons instead. Consider:
  (define inf-list$
    (lambda (n)
      (cons n (lambda () (inf-list$ (+ n 1))))))
  (define take$ 
    (lambda (n S$ acc)
      (if (or (null? S$) (= n 0))
          (take$ (- n 1) ((cdr S$)) (append acc (list (car S$)))))))
  (define take-nth$ 
    (lambda (n S$)
       (if (or (null? (cdr S$)) (= n 0))
           (car S$)
           (take-nth$ (- n 1) ((cdr S$))))))
  (define take-cons$  ;; no append
    (lambda (n S$ acc)
      (if (or (null? S$) (= n 0))
          (take-cons$ (- n 1) ((cdr S$)) (cons (car S$) acc)))))
  (take$ 1000000 (inf-list$ 1) '())
takes minutes while
  (take-nth$ 1000000 (inf-list$ 1))
completes almost instantly and so does
  (take-cons$ 1000000 (inf-list$ 1) '())
(but it takes a while to print the whole list). The conclusion is that append is the culprit. Stay away from append if you have the need for speed.
    Conner Pike
        question: I want to see an example where an operation causes output types to be more restrictive than input types.
        answer: OK, your wish is my command. Consider:
  [franco@franco Downloads]$ ghci
  GHCi, version 7.8.3:  :? for help
  Loading package ghc-prim ... linking ... done.
  Loading package integer-gmp ... linking ... done.
  Loading package base ... linking ... done.
  Prelude> let a = [1,2,3,4,5]
  Prelude> a
  Prelude> :t a
  a :: Num t => [t]
So, a is a list of numbers. But now add something to the list
  Prelude> let b = (6/5):a
  Prelude> b
  Prelude> :t b
  b :: Fractional a => [a]
Now b is the same list as a except it has a (6/5) in front and the type of b is a list of Fractionals. It is illegal to do this:
  Prelude> let c = 'A':a
  Prelude> let c = 5.6:a
works and c has the same type as b.
  Prelude> c
Finally try this
  Prelude> let d = pi : a
  Prelude> d
The type of d is more restrictive as this shows:
  Prelude> :t d
  d :: Floating a => [a]
    Conner Pike
        question: Which is faster in creating a huge list, Scheme or Haskell?
        answer: This is not really a fair question because Haskell is really lazy when it comes to building lists but the following is intended to develop some insight into list building and displaying in both languages. Consider the Scheme code for building a list tail recursively:
  (define ll
    (lambda (n acc)
      (if (= n 0)
      (ll (- n 1) (cons n acc)))))
and run it like this:
  (define a (ll 1000000 '()))
The list is built in about a second. If you type a at the Scheme prompt, the list will appear but it takes about 20 seconds to print it to the console. Now consider the Haskell code:
  ll 0 acc = acc
  ll n acc = ll (n-1) ((n-1):acc)
which is essentially the same as the Scheme code. Doing this:
  let a = (ll 1000000 [])
completes absolutely instantly - there are lambdas all over the place!! But now put the lambdas to work like this:
  Prelude> a
and get some coffee - about 1 minute 10 seconds to print. Now hold onto your hat. Consider the Scheme code for producing the list in continuation passing style:
  (define ll$
    (lambda (n)
      (if (= n 0)
          (cons n '())
	  (cons n (lambda () (ll$ (- n 1)))))))
and define take$ to build and print the entire list tail recursively
  (define take$
    (lambda (S$ acc)
      (if (null? (cdr S$))
          (take$ ((cdr S$)) (cons (car S$) acc)))))
then "wind up" a list like this
  (define a (ll$ 1000000))
instantly, just the same as for Haskell. But releasing the spring like this:
  (take$ a '())
only takes 27 seconds to print the list - almost as fast as without the lambdas but way faster than the time it takes Haskell to do the same.
Paul Erdos
Ladies on Campus
Oscar Robinson