Tail call optimization and OO

From: Matthew D Swank (akopa-is-very-much-like-my-mail-address_at_c.net)
Date: 03/24/05 

Date: Thu, 24 Mar 2005 11:39:42 -0600

Matthias Felleisen gave a presentatation at ECOOP 2004 titled
"Functional Objects"
(http://www.ccs.neu.edu/home/matthias/Presentations/ecoop2004.pdf).

In it he points to what he sees as deficiencies in OO languages and
practice that could be addressed with ideas from functional programming.
In Part III (starting at slide 54) he presents an example that is
supposed to show that an OO language is deficient if it does not provide
tail call optimization.

A paraphrase of the example: It is a good idea to replace a
union with a hierarchy of classes. For example we can think
of lists as an abstract list --'alist', and two concrete
subclasses: 'empty' and 'cons-cell'. Felleisen gives his
implementation in Java (which seems to have a few errors
in the slides). I give a CLOS equivalent:

(defclass alist () ())

(defclass empty (alist) ())

(defclass cons-cell (alist)
  ((head :initarg :head :accessor the-head)
   (tail :initarg :tail :accessor the-tail)))

(defgeneric how-many (o a))
(defgeneric cons-length (sequence))

(defmethod how-many ((o cons-cell) a)
  (how-many (the-tail o) (+ 1 a)))

(defmethod how-many ((o empty) a)
  a)

(defmethod cons-length ((sequence alist))
  (how-many sequence 0))

(defun kons (kar kdr)
  (let ((cell (make-instance 'cons-cell :head kar :tail kdr)))
    cell))

;; just a util to make large lists
(defun make-alist (n cons)
  (if (> n 0)
      (make-alist (- n 1) (kons 1 cons))
    cons))

(defvar naught (make-instance 'empty))

Of course the implementation of 'how-many' breaks on large list in
languages (and lisp implementations) with out tail call elimination.
(Felleisen makes the blanket claim that how-many breaks in CLOS!)

My question: is this a straw-man? Felleisen implements
a "fix" by implementing 'how-many' in 'alist' by using a for
loop (which terminates by explicitly testing for an
instance of 'empty'), and claims this violates principles of
good object oriented design.

Thanks,

Matt 

-- 
"You do not really understand something unless you can 
explain it to your grandmother." — Albert Einstein.

Relevant Pages

  • Re: EE Student, Edit, Proposal Masters, Help (concepts of functional programming, symbolic programmi
    ... A few comments on Symbolic and Functional Programming ... Symbolic programming languages fall under two categories, ... types, lists, expressions, primitives and variables. ... The assignment chain is not altered by evaluation. ...
    (sci.math.symbolic)
  • Re: Static vs Dynamic
    ... The type system in SML has the notion of ``parametric polymorphism'' ... functions that operate on lists in general, ... polymorphism, and for ease of type inference. ... Other languages with similar goals include Objective CAML, ...
    (comp.lang.lisp)
  • Re: mot de passe root
    ... > poster's fellow nationals gently reminds them that it's an English ... Posts in other languages were historically entirely welcome, ... lists was because they were likely to get better results there, ... enough of a French posting to understand the problem and proposed ...
    (freebsd-questions)
  • Re: Reminder, blatant ad
    ... >>> a) The problem is naturally formulated in terms of named lists of items ... the programmig languages are many. ... What works for me is what I would call a di-graph of trees (a tree on ... I think declarative languages are ...
    (comp.databases.theory)
  • Re: UNIX, C, Perl
    ... you're misrepresenting him by converting statements that say that "much" code should be done in other languages into statements that "all" code should be done in other languages. ... Since a lot of other smart people who like programming in C agree with him in that regard, you might want to consider the possibility that it's the nature of the proposed change that is the problem, not just the simple fact that it is a change. ... although it still has deficiencies even for that. ... "It is a mistake to try to push C as a solution for any programming problem other than the systems programming tasks that it was designed for, although it still has deficiencies even for that. ...
    (comp.lang.c)