FP, OO and relations. Does anyone trump the others? 
Author Message
 FP, OO and relations. Does anyone trump the others?

It is actually rather easy to implement an OO system in a functional
language.

According to the classical definition,
"An object has state, behavior, and identity; the structure and
behavior of similar objects are defined in their common class; the
terms instance and object are interchangeable".
[See the OO FAQ, http://www.{*filter*}dyne-object-sys.com/oofaq2/ ]

Let's consider behavior, which is often understood as an ability to
send an object a message to which it replies. To put in other terms,
we invoke a dispatcher function of the object and pass it an indicator
of a message along with other parameters. The result of that function
is the reply. As far as the external world is concerned, this
dispatcher function is the representation of the object -- it *is* the
object. Well, an object has to encapsulate and maintain a state --
thus the dispatcher function should be a closure. The identity aspect
depends: if the dispatcher function is a pure function, or if it can
mutate its own state ("closed" variables) in response to some
messages.

In 1992 Ken{*filter*}ey wrote a fascinating paper "Scheming with Objects"
[ ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/swob.txt ]
It starts as follows
"There is a saying--attributed to Norman Adams--that 'Objects are a
poor man's closures.' In this article we discuss what closures are and
how objects and closures are related, show code samples to make these
abstract ideas concrete, and implement a Scheme Object System which
solves the problems we uncover along the way."

His paper really implements an OO system in Scheme. It relies heavily
on custom syntax forms though, to make definitions of objects and
classes as familiar as possible. Listing 1 (below) shows a far lighter
version. It deliberately uses only most basic Scheme constructions. It
implements a delegation-based OO system (as found in Self and
Javascript).
In Listing 1, the closures are not pure (they can mutate their own
state). However, one can just as easily implement the same OO system
in a pure functional language: Listing 2. Well, it's Scheme again, its
purely functional subset. Listing 1 is a part of a post (which I
didn't get around to finish) about contra-variance and why it is
important.

Note that Listing 2 demonstrates a fully-fledged OO system with
encapsulation, object identity, inheritance and polymorphism. And no
assignments!

It is possible to implement a two-level OO system, with classes and
instances, in FP. CLOS is a very advanced example of a OO system with
generic functions and multi-methods.



Quote:

> How do we define that a paradigm can model another one? After all
> one can write an interpreter of any real language using any other
> Turing-complete language. We don't want to say that the C language
> models functional and OO paradigms only because compilers of
functional
> and OO languages use C as their target languages.

> We want the translated programs to "integrate" well enough with the
> implementing language. I'm afraid that it must be very informal...

Matthias Felleisen wrote a paper exactly on that subject:
"On the Expressive Power of Programming Languages"
[ http://www.*-*-*.com/ ] He came up
with an interesting, formal definition that lets you tell
when one language is strictly more expressive than the other.
He _proved_ for example that a call-by-value lambda-calculus
is strictly less expressive than call-by-name lambda-calculus
(if I remember correctly).

Listing 1. A trivial delegation-based OO system (with encapsulation
and inheritance). Object's identity is decided by eq? predicate. A
set-x! message changes object's state but does not affect its
identity.

(define (make-point-2D x y)
  (define (get-x) x)
  (define (get-y) y)
  (define (set-x! new-x) (set! x new-x))
  (define (set-y! new-y) (set! y new-y))
  (lambda (selector . args)     ; a dispatcher
      (case selector
        ((get-x) (apply get-x args))
        ((get-y) (apply get-y args))
        ((set-x!) (apply set-x! args))
        ((set-y!) (apply set-y! args))
        (else (error "don't understand " selector)))))

(define (make-point-3D x y z)
                ; that is, point-3D _inherits_ from point-2D
  (let ((parent (make-point-2D x y)))
    (define (get-z) z)
    (define (set-z! new-z) (set! z new-z))
    (lambda (selector . args)
      (case selector
        ((get-z) (apply get-z args))
        ((set-z!) (apply set-z! args))
                ; delegate everything else to the parent
        (else (apply parent (cons selector args)))))))

(define a-point-2D (make-point-2D 5 6))
(define a-point-3D (make-point-3D 7 8 9))
(a-point-2D 'get-x) => 5
(a-point-3D 'get-x) => 7
(a-point-2D 'set-y! 10)
(a-point-3D 'set-z! 11)
(a-point-2D 'get-y) => 10
(a-point-3D 'get-z) => 11
(define b-point-2D (make-point-2D 5 10))

        ; a-point-2D and b-point-2D currently have the same state
(equal? (list (a-point-2D 'get-x) (a-point-2D 'get-y))
        (list (b-point-2D 'get-x) (b-point-2D 'get-y))) ==> #t

        ; but they are different objects
(eq? a-point-2D b-point-2D) ==> #f

Listing 2. The same but in a pure functional style. In addition, the
following system implements polymorphism. Each message returns a list;
its head is an object with a new state, having processed the message;
the rest of the list are the results of the message if any. Objects
identity is decided by an eq? predicate applied to the result of an
'identify' message. As before, a "set-x" method "changes" object's
state but preserves its identity -- in a manner of speaking, of
course.

                ; functional substitution in a assoc list
(define (new-mmap mmap tag new-body)
  (cond
   ((null? mmap) '())
   ((eq? tag (caar mmap))       ; replacement
    (cons (cons tag new-body) (cdr mmap)))
   (else (cons (car mmap) (new-mmap (cdr mmap) tag new-body)))))

(define (make-point-2D x y)
  (define (my-identity) x)
  (define message-map
    `((get-x . ,(lambda (self) (list self x)))
      (get-y . ,(lambda (self) (list self y)))
      (set-x . ,(lambda (self new-x)
                  (list
                   (make-dispatcher
                    (new-mmap (self 'mmap) 'get-x
                              (lambda (self) (list self new-x)))))))

      (set-y . ,(lambda (self new-y)
                  (list
                   (make-dispatcher
                    (new-mmap (self 'mmap) 'get-y
                              (lambda (self) (list self new-y)))))))
      (identity . ,(lambda (self) (list self my-identity)))
      (my-class . ,(lambda (self) (list self "point-2D")))
      (of-class . ,(lambda (self) (self 'my-class))) ; an example of
                        ; using my own method
      ))
  (define (make-dispatcher mmap)
    (define (dispatcher selector . args)
      (cond
       ((eq? selector 'mmap) mmap)
       ((assq selector mmap) =>
        (lambda (handler-ass)
          (apply (cdr handler-ass) (cons dispatcher args))))
        (else
         (error (dispatcher 'my-class) " does not understand "
selector))))
    dispatcher)
  (make-dispatcher message-map))

(define (print-x-y obj)
  (define (rev-apply lst handler) (apply handler lst))
  (rev-apply (obj 'get-x)
             (lambda (obj x)
               (rev-apply (obj 'get-y)
                          (lambda (obj y)
                            (rev-apply (obj 'my-class)
                                       (lambda (obj my-class)
                                         (list my-class x y))))))))

(define p (make-point-2D 5 6))
(define p1 (make-point-2D 5 6))
(p1 'of-class) ==> (#<procedure p1> "point-2D")
(p 'get-x)     ==> (#<procedure p> 5)
(p1 'get-x)    ==> (#<procedure p1> 5)

(print-x-y p)   ==> ("point-2D" 5 6)

; states happen to be the same
(equal? (print-x-y p) (print-x-y p1))   ==> #t

; but p and p1 are different objects
(eq? (cadr (p 'identity)) (cadr (p1 'identity))) ==> #f

(define pm (car (p 'set-x 10)))
(print-x-y pm)  ==> ("point-2D" 10 6)

; States differ, identities are the same
(equal? (print-x-y p) (print-x-y pm)) ==> #f
(eq? (cadr (p 'identity)) (cadr (pm 'identity))) ==> #t

; illustrating inheritance and polymorphism

(define (make-point-3D x y z)
  (define message-map
    (append
     `((get-z . ,(lambda (self) (list self z)))
       (set-z . ,(lambda (self new-z)
                   (list
                    (make-dispatcher
                     (new-mmap (self 'mmap) 'get-z
                              (lambda (self) (list self new-z)))))))
       (my-class . ,(lambda (self) (list self "point-3D")))
      )
     ((make-point-2D x y) 'mmap)))      ; the superclass

  (define (make-dispatcher mmap)
    (define (dispatcher selector . args)
      (cond
       ((eq? selector 'mmap) mmap)
       ((assq selector mmap) =>
        (lambda (handler-ass)
          (apply (cdr handler-ass) (cons dispatcher args))))
        (else
         (error (dispatcher 'my-class) " does not understand "
selector))))
    dispatcher)
  (make-dispatcher message-map))

(define q (make-point-3D 1 2 3))
(print-x-y q)  ==>  ("point-3D" 1 2)
(q 'get-z)     ==>  (#<procedure q> 3)

; use of inherited methods....
(let ((obj (car ((car (q 'set-x 11)) 'set-z 12))))
  (append (print-x-y obj) (cdr (obj 'get-z))))
==> ("point-3D" 11 2 12)

(q 'of-class) ==> (#<procedure q> "point-3D") ; notice polymorphism!!!
; The of-class method is implemented in point-2D yet it prints
; "point-3D" (because the my-class method it uses is overridden)

I can elaborate further, but it's late and I want to go home...

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Sun, 16 Jun 2002 03:00:00 GMT  
 FP, OO and relations. Does anyone trump the others?

Quote:
> In 1992 Ken{*filter*}ey wrote a fascinating paper "Scheming with Objects"
> [ ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/swob.txt ]

As I understand it and your Listings 1 & 2, they all heavily rely on
dynamic typing. I don't see how to simulate inheritance in Haskell
while preserving static typing... Of course it can be done with
simulated dynamic typing.

Haskell++ < http://www.*-*-*.com/ ~rjmh/Software/h++.html>
provides type safe inheritance, but because it's only a "stateless"
preprocessor written in 4.6kB of code (+ 3.5kB of a parsing library),
it requires explicit mentioning of methods to be inherited.

--

 #o#    \__/    Kowalczyk | GCS/M d- s+:--  a22  C+++$  UL++>++++$  P+++
#o###    ^^     L++>++++$ E- W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y?
  I    QRCZAK   PGP+ t 5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++  y-



Sun, 16 Jun 2002 03:00:00 GMT  
 FP, OO and relations. Does anyone trump the others?


Quote:
> As I understand it and your Listings 1 & 2, they all heavily rely on
> dynamic typing. I don't see how to simulate inheritance in Haskell
> while preserving static typing... Of course it can be done with
> simulated dynamic typing.

Ken{*filter*}ey's paper as well as Listings 1 and 2 of the previous message
implemented a dispatcher (aka record-) based approach to a OO system. The
other one is that of generic functions (which is used in CLOS). There
indeed appears to be a difficulty with the dispatcher in Haskell.

In this approach, an object is a closure, which encapsulates and
maintains object's state. The closure can be applied to input messages,
which yields an output message and another closure (perhaps the same,
perhaps different if the message changed the state of the object). Thus
the dispatcher closure should have the following type:

data Point_2D = Point_2D_In -> (Point_2D, Point_2D_Out)

I'm afraid Haskell type system may not bear the above declaration. Thus
the trouble is not a static type system per se, but the paradoxical
combinator so to speak. Cayenne probably would not have any trouble with
Point_2D. I also read that it's possible to introduce the Y combinator
and similar-"typed" functions in ML, to a certain extent.

Point_2D_In is an algebraic (union) datatype describing all possible
input messages:

data Point_2D_In = Get_x | Set_x Int | Get_y | Set_y Int | Get_class_name

By the same token Point_2D_Out describes all possible output messages.

data Point_3D_In = Point_2D_In | Get_z | Set_z Int

This declaration if works out makes things neat: a type of messages for a
3D point is a superset of messages for the 2D point.

Unfortunately the actual implementation of inheritance and polymorphism
involves even more recursive functional types. Thus any hope of seeing a
dispatcher work in Haskell dwindles. Generic functions seem to be the
best. They are also more general as they potentially support multi-
methods.

Happy Y2K!

Sent via Deja.com http://www.*-*-*.com/
Before you buy.



Tue, 18 Jun 2002 03:00:00 GMT  
 FP, OO and relations. Does anyone trump the others?

Quote:

>Thus the dispatcher closure should have the following type:

>data Point_2D = Point_2D_In -> (Point_2D, Point_2D_Out)

>I'm afraid Haskell type system may not bear the above declaration.

That's easily solved:

        data Point_2D = Mk_Point_2D (Point_2D_In -> (Point_2D, Point_2D_Out))

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Tue, 18 Jun 2002 03:00:00 GMT  
 FP, OO and relations. Does anyone trump the others?

:>Thus the dispatcher closure should have the following type:
:>
:>data Point_2D = Point_2D_In -> (Point_2D, Point_2D_Out)
:>
:>I'm afraid Haskell type system may not bear the above declaration.

: That's easily solved:

:    data Point_2D = Mk_Point_2D (Point_2D_In -> (Point_2D, Point_2D_Out))

For the non-Haskell programmer this means "A Point_2D datum is
expressed by the constructor Mk_Point_2D, (pronounced: make point 2d),
parameterized by a function of the given type." Correct?

--



Tue, 18 Jun 2002 03:00:00 GMT  
 FP, OO and relations. Does anyone trump the others?

Quote:


>:>Thus the dispatcher closure should have the following type:
>:>
>:>data Point_2D = Point_2D_In -> (Point_2D, Point_2D_Out)
>:>
>:>I'm afraid Haskell type system may not bear the above declaration.

>: That's easily solved:

>:    data Point_2D = Mk_Point_2D (Point_2D_In -> (Point_2D, Point_2D_Out))

>For the non-Haskell programmer this means "A Point_2D datum is
>expressed by the constructor Mk_Point_2D, (pronounced: make point 2d),
>parameterized by a function of the given type." Correct?

Yes.  

I'll elaborate a little more.
The first declaration quoted above is a syntax error.
Probably what was meant was

        type Point_2D = Point_2D_In -> (Point_2D, Point_2D_Out)
        ^^^^

which defines `Point_2D' as a type alias (like `typedef' in C).
The alternative that I suggested defines `Point_2D' as a new
data type.  In Haskell, you're allowed to have recursive data types,
but you can't have recursive type aliases.

Actually my suggestion of using `data' is sub-optimal.
The reason is that whenever you apply the constructor `Mk_Point_2D',
the compiler will allocate a new object on the heap.
Haskell also has a `newtype' declaration, which is like
a cross between the `type' and `data' declarations.
With a `newtype' declaration, e.g.

    newtype Point_2D = Mk_Point_2D (Point_2D_In -> (Point_2D, Point_2D_Out))

the semantics are almost exactly the same as with a `data'
declaration, but operationally the constructor application
will be a no-op; the compiler will not need to allocate
a cell on the heap for each `Point_2d' object.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Thu, 20 Jun 2002 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. FP, OO and relations. Does anyone trump the others?

2. FP, OO and relations. Does anyone trump the others?

3. OO and FP (was subtyping in FP)

4. Doing graphs in FP

5. relation between declarative imperative and OO

6. relation between declarative imperative and OO

7. FP as enhancement of OO

8. FP's and OO and generic programming

9. OO and FP - mutually exclusive?

10. FP/OO

11. OO and FP - mutually exclusive?

12. Anyone used SB/others

 

 
Powered by phpBB® Forum Software