Chapter2

Review OOP

In the traditional OOP, an object is a data structure that stores values called the (instance) attribute of the object, that is also associated with functions called (instance) methods that operate of this data.

The OOP was introduced as a way to organize data that promotes encapsulations, separating private concerns of how this data is organized from the public interface that determine how other code may interact with the data. Unlike the pure functions, a method in OOP always takes a special argument, an associated object that we say is calling the method. Though internal attributes of an object are generally not accessible from outside the object, they are accessible from within the body of methods that the object calls.

Historically, the centrality of the object itself to call methods and access attributes led to the metaphor or entities sending and responding to message for modeling computation.

(define (point msg)
    (cond [(equal? msg 'x) 10]
          [(equal? msg 'y) -5]
          [else "Unrecognized message"]))
> (point 'x)
10
> (point 'y)
-5

Adding attributes

This “point object” is very simple, it does not contain any methods and its attributes are all hard-coded. To solve the latter problem, the solution is to make it a class, a template that specifies both the attributes and methods for a type of object. In class-based OOP, every object is an instance of a class, obtaining their attributes and methods from the class definition. Objects are created by calling a class constructor, a function whose purpose is to return a new instance of that class, often initializing all the new instance’s attributes.

In the language of functions, a constructor for Point is a function that takes two numbers, and returns a function analogous to the one above, except with the 10 and 5 replaced by the constructor’s arguments.

;; constructor for Point
;; Input: x y
;; Output: Function
(define (Point x y)
    (lambda (msg)
        (cond [(equal? msg 'x) x]
              [(equal? msg 'y) y]
              [else "Unrecognized message"]))
    )
> (define p (Point 10 20))
> (p 'x)
10
> (p 'y)
20

Recall what we have seen before, x and y are free identifier in the returned function meaning that x and y must have values bound in a closure when the Point constructor returns. Moreover, because the identifiers x & y are local to the Point constructor, even though their values are stored in the closure, once the constructor has returned they can’t be accessed without passing a message to the object. This is the property of closures that enables encapsulation: even though both x and y values are accessible by passing the right messages to the object, it is certainly possible to implement “private” attributes in this model.

Adding methods

Functions are first-class values in the functional languages meaning that we can add methods to the Point class just in the same way as we were doing for adding attributes. A keynote here is that in the classical OOP we expect instance methods have full access to instance attributes. The functional programming is also possible for doing this. The reason is similar to what we have discussed above, the attributes to a class are free identifiers thus, they must be bound before the function return.

(define (Point x y)
  (lambda (msg)
    (cond [(equal? msg 'x) x]
          [(equal? msg 'y) y]
          [(equal? msg 'to-string)
           (lambda () (format "(~a, ~a)" x y))]
          [(equal? msg 'distance)
           (lambda (other-point)
             (let ([dx (- x (other-point 'x))]
                   [dy (- y (other-point 'y))])
               (sqrt (+ (* dx dx) (* dy dy)))))]
          [else "Unrecognized message"])))
> (define p (Point 3 4))
> (p 'to-string)
<procedure>
> ((p 'to-string))
"(3, 4)"
> ; Note that (p 'distance) returns a function, so the expression
> ; below is a *nested function call*
> ((p 'distance) (Point 0 0))
5

Pattern-based macros

Programmer usually treat functions as entities that take value as inputs and return a new value. There is a limitation of the function which many people have ignored, or they do not aware that is the syntax and semantic of the functions are defined by the programming language itself, and not the programmer who writes them.

On the other hand, a macro is a function that operates on the program source code: a macro takes code as input and returns new code. Many languages allow programmers to define their own macros, just as they can define their own function. In such languages, there is an additional step between the parsing source code and generation of machine code or runtime evaluation, called macro expansion, in which macros are applied to the AST to generate a new AST.

The main use of macro we’ll see is to introduce new syntax into a programming language.

The first simple macro we will write is the list comprehension in Haskell / Python

-- In Haskell
>>> [x + 2 | x <- [0, 10, -2]]
[2, 12, 0]

# In Python
>>> [x + 2 for x in [0, 10, -2]]
[2, 12, 0]

We will use the syntax of list comprehension in Haskell as the example

<list-comp> = "[" <out-exp> "|" <id> "<-" <list-exp> "]"

There is no list-comprehension in the Racket, but we can implement it using the Racket’s macro system. Let us do this in the backward order.

We first introduce the expected output

 ; haskell-like style
 > (list-comp (+ x 2) : x <- (list 0 10 -2))
 '(2, 12, 0)
 ; python-like style
 > (list-comp (+ x 2) for x in (list 0 10 -2))
 '(2, 12, 0)

We can tell that so far the list comprehension works in the same way as the map.

 (list-comp (+ x 2) : x <- (list 0 10 -2))
 ; This is essentially the same as
 (map (lambda (x) (+ x 2)) (list 0 10 -2))

Let us use the pattern-matching to describe the general syntax, and the expected behaviour

 (list-comp <out-exp> : <id> <- <list-exp>)
 (map (lambda (<id>) (<out-exp>)) <list-exp>)

The pattern-matching here is the core for writing the macro since it tell us what syntactic transformation the interpreter will need to perform: everytime it sees a list comprehension, it should transform it into a call to map.

Finally, we can write a macro in Racket that does the syntactic transformation. The macro we use is the pattern-based macro

 ; define-syntax defines a name binding for a new macro
 ; The name it takes is the binding of the new macro
 ; Following by the name is the macro expansion
 (define-syntax list-comp
   ; syntax-rules takes at least two arguments
   ; The first is a list of literal keywords
   ; Followed by one ore more syntax patterns
   (syntax-rules (: <- for in)
     ; Every syntax pattern starts with the syntax pattern to match
     ; Followed by a template
     ; Telling the interpreter how to do the transformation
     [(list-comp <out-exp> : <id> <- <list-exp>)
      (map (lambda (<id>) <out-exp>) <list-exp>)]
     ; Another syntax pattern for python-like style
     [(list-comp <out-exp> for <id> in <list-exp>)
      (map (lambda (<id>) <out-exp>) <list-exp>)]
     )
   )

Pattern Variables & Literal Keyword

The syntax pattern rule makes use of both pattern variables and literal keywords.

Pattern Variable: An identifier that can be bound to an arbitrary expression when the pattern matches; We will use the convention of enclosing angle brackets for denoting the pattern variable. The <id>, <out-expr>, <list-exp> in the above macro are all pattern variables. During macro expansion, when Racket finds a pattern-match, it binds the pattern variable to the corresponding expression, and then substitutes this expression where ever the variable appears in the rule’s template. In macro expansion, expressions aren’t evaluated before they are bound! All the macro does is transforming code not about evaluation. When we say that an expression is bound to a pattern variable, we literally mean that entire expression is bound to the variable, not the value of the expression.

Literal Keyword: part of the syntax that must appear literally in the syntax expression. If we try to use the list-comp without the keywords, we get a syntax error the Racket interpreter does not recognize the expression, because it no longer pattern-matches our rule:

> (list-comp (+ x 2) ` x -> (list 0 10 -2))
list-comp: bad syntax ...

Multiple pattern rules

The list comprehension in Haskell/Python all support the optional filtering of the input list

-- In Haskell 
>>> [x + 2 | x <- [1, 20, -1], x >= 0]
[3, 22]

# In Python
>>> [x + 2 for x in [1, 20, -1] if x >= 0]
[3, 22]

We can extend the macro by adding new syntax rules to support the filter

   (define-syntax list-comp
      ; we need to add if into literal keywords
      (syntax-rules (: <- for in if)
        [(list-comp <out-exp> : <id> <- <list-exp>)
         (map (lambda (<id>) <out-exp>) <list-exp>)]
        [(list-comp <out-exp> for <id> in <list-exp>)
         (map (lambda (<id>) <out-exp>) <list-exp>)]
        ; new syntax rules
        [(list-comp <out-exp> : <id> <- <list-exp> if <cond>)
         (map (lambda (<id>) <out-exp>) (filter (lambda (<id>) <cond>) <list-exp>))]
        ; python-like filters
        [(list-comp <out-exp> for <id> in <list-exp> if <cond>)
         (map (lambda (<id>) <out-exp>) (filter (lambda (<id>) <cond>) <list-exp>))]
      )
   )
> (list-comp (+ x 2) : x <- (list 1 20 -1) if (>= x 0))
'(3 22)
> (list-comp (+ x 2) for x in (list 1 20 -1) if (>= x 0))
'(3 22)

Text-based vs. AST-based macros

Macros in C, C++ operate on the source rather than a parsed AST. We will see some fundamental differences on the text-based macros and AST-based macros.

Consider a simple macro in C

 #include <stdio.h> 
 #define double(x) 2 * x
   
 int main(void){
     int a = 10;
     printf("%d\n", double(100));
     printf("%d\n", double(a));
     return 0;
 }

The above examples work fine if we only provide with singe expression. In terms of macro expansion, the x is replaced by 100 and a. Then, the C compiler performs 2 * 100 and 2 * a.

There is a problem raised if we call double (5 + 5); this will return 15 not 20!

The reason behind this is simple the macro replaces x with 5 + 5, this results the expression to be evaluated is 2 * 5 + 5 which is 15 not 20.

We can parenthesize macro variables to address this problem.

#define double(x) 2 * (x)

In terms of AST-based macro, it also substitutes the expression with 5 + 5, but since the code is substituted in the AST level, the structure of the program has already been determined, we do not need to worry the problem above.

A simple AST Tree
     *
    / \
   2   x
After substituion
     *
    / \
  2  5 + 5
To furthur expand the AST
     *
    / \
   2   +
       /\
      5  5

Another simple macro in C

#include <stdio.h> 
#define swap(a, b) int temp = a; a = b; b = temp;
int main(void){
     int x = 0, y = 10;
     swap(x, y);
     printf("x is now %d y is now %d\n", x, y);
     return 0;
}

The above works fine, however the code will fail if we include more than one call of swap. It will raise an error of redefinition of temp. The reason is that each use of the macro declares a local variable temp, which is a compilation error. C introduces local scopes for the macro by adding curly braces. The solution to the above problem is enclosing the macro body in curly braces.

#define swap(a, b){int temp = a; a = b; b = temp;}

There is another problem of the above macro even after introducing the local scope. The problem is one of the variables we wanted to swap was named temp.

#include <stdio.h> 
#define swap(a, b){int temp = a; a = b; b = temp;}
int main(void){
     int x = 0, temp = 10;
     swap(x, temp);
     printf("x is now %d temp is now %d\n", x, temp);
     return 0;
}

In short words, x and temp will not be swapped.

To explain this, we will take a look on the text substitution of swap(x, temp);

{int temp = x; x = temp; temp = temp;}

In this case, all references to temp in the macro are the block-local temp, not the temp that was initialized to 10 at the top of main. So the local temp is initialized to the current value of x which is 0, then x is assigned that value(0), and then temp is assigned its current value. After the block executes, the values of x and temp haven’t changed at all.

The solution requires declaration of temp before using this macro.

#include <stdio.h>
#define swap(a, b){int temp = a; a = b; b = temp;}
int main(void){
   int x = 10, y = 20, temp;
   swap(x, y);
   printf("x is now %d, y is now %d\n", x, y);
   return 0;
}

Above examples have demonstrated various ways that the C macro can interact with the scope in which it is used.

Introducing names into the outer scope (The one which cause the redefinition error)
Shadowing identifiers that are passed as arguments to the macro (The one which fails to swap value)
Accessing and mutating values from the outer scope

The ability for a C macro to refer to identifiers defined in an outer scope is known as name capture.

More importantly, the behaviour of these macros shows that the Identifiers in C Macros follow dynamic scope

Whereas, the Racket macro still obeys lexical scope which is known as the hygienic macros.

We will use a simple example to demonstrate the static scope behaviour of the Racket.

(define-syntax add-temp
   (syntax-rules ()
      [(add-temp <x>)
         (+ <x> temp)
      ]
   )
)

(let* ([temp 10]) (add-temp 100))
Error temp: undefined;
cannot reference an identifier before its definition

Indeed, this shows that identifier cannot be bound dynamically where the macro is used. This is true for all Racket macros: free identifiers in the macro obey lexical scope, meaning they are bound to whatever identifier is in scope where the macro is originally defined, and cannot accidentally bind name when it is used. As a consequence of macro hygiene, identifiers defined within a macro body are not accessible outside the macro body - that is, they’re local to the macro even when a straight textual substitution would suggest otherwise.

(define-syntax defs
   (syntax-rules ()
      [(defs)
       (begin
         (define x 1)
         (define y (+ x 10))
         (+ x y)
       )      
      ]
   )
)
(defs) ; The evaluate to 12
x ; This is an error! both x and y are local to the macro they cannot be accessed outside

Macro ellipses

It is often the case that we want a macro that can be applied to arbitrary number of expression for instance, and, or, cond. A challenge is that we cannot write an explicit pattern variable for each expression we expect to match. Instead, we can use the ellipsis … in a pattern: ... matches zero or more instances of the pattern , which could be a pattern variable or a complex pattern itself.

Here is one example of using the ellipsis in a recursive macro that implements cond in terms of if.

(cond [c1 x1]
      [c2 x2]
      [else y])
; This can be expanded as a if nested inside another if
(if c1
    x1
    (cond [c2 x2]
          [else y])
   )
; Eventually expanding to
(if c1
    x1
   (if c2
       x2
       y))

Here is how to write this in a macro

(define-syntax my-cond
  (syntax-rules (else)
    [(my-cond) (void)]
    [(my-cond else <val>) <val>]
    [(my-cond [<test> <val>] <rest> ...)
     (if <test> <val> (my-cond <rest> ...))]))

Macro for Object

Adding attributes

Let us look the Point we created above. For now, let we concentrate on the abbreviated Point without any methods.

(define (Point x y)
    (lambda (msg)
        (cond [(equal? msg 'x) x]
              [(equal? msg 'y) y]
              [else "Unrecognized message"])))

The goal at this stage is to use the macro to hide / abstract the detail of defining a constructor function, and the message handling to enable easy declaration.

Start with the new syntax we are expecting

(class Point (x y))

Write the skeleton of the macro

(define-syntax class
   (syntax-rules (class)
      [(class <class-name> (<attr> ...))
         (define (<class-name> <attr> ...)
            (lambda (msg)
               (cond [???]
                     [else "Unrecognized message"])))]))

The remaining problem is to fill the cond. A problem here is that since we allow arbitrary number of attributes, how can we generate query expression for every attribute? It turns out that macro ellipses support this behaviour.

(define-syntax class
   (syntax-rules (class)
      [(class <class-name> (<attr> ...))
         (define (<class-name> <attr> ...)
            (lambda (msg)
               (cond [(equal? msg (quote <attr>)) <attr>]
                     ; Repeat the previous expression once per expression
                     ; in <attr> ..., replacing just occurrences of <attr>
                     ...
                     [else "Unrecognized message"])))]))

It turns out that we can refactor the code by moving all the query on cond into a dictionary

(define-syntax class
   (syntax-rules (class)
      [(class <class-name> (<attr> ...))
         (define (<class-name> <attr> ...)
            (lambda (msg)
               (let* ([__dict__ (make-immutable-hash (list (cons (quote <attr>) <attr>) ...))])
                     (hash-ref __dict__ msg))))]))

Usage

(class Point (x y))
; Macro Expansion
; It creates the constructor function for Point in top level
(define (Point x y)
 (lambda (msg)
  (let* ([__dict__
          (make-immutable-hash 
           (list (cons (quote x) x) (cons (quote y) y)))]))
   (hash-ref __dict__ msg)
 )
)
; To use it
; Call the constructor to create a instance in OOP
; Note p is actually the lambda function in the constructor
; p takes the responsibility for message handling
(define p (Point 10 20 30))
> (p 'x)
10

# A simplified python implementation
def macro(class_name, *attrs):
 """
 The macro is a function which takes a class name and attribute names of the
 class.  This function creates a function in the global scope with the same
 name as the <class_name> includes the name binding of attrs which acts
 similar to the init function in a class.
 :param class_name: name of a class
 :param attrs: name of attributes
 :return: None
 """
 def init(*args):
     """
     The init is a function which takes value for binding to the attributes in
     a class.  This function returns a function which is used for accessing
     the attributes enclosed in a class
     :param args: value of attributes
     :return: callable
     """        
     def msg_handle(msg):
         o_dict = {attrs[i]: args[i] for i in range(len(attrs))}
         return o_dict.get(msg, 'No such attribute')
     # The init function returns the function for message handling
     return msg_handle
 # The macro creates a init function in the top level
 globals()[class_name] = init
>>> macro('Point', 'x', 'y')
>>> p = Point(1, 2)
>>> p('x')
1

Adding methods

The new syntax we want to introduce is

(class <class-name> (<attr>  ...)
 (method (<method-name> <param> ...) <body>) ...
)

The expected expansion

(class Point (x y)
 (method (size)
     (sqrt (+ (* x x) (* y y)))
; The expansion
(define Point (x y)
 (lambda (msg)
  (let* ([__dict__
         (make-immutable-hash 
          (list 
           (cons (quote x) x) 
           (cons (quote y) y)
           (cons (quote size) (lambda () (sqrt (+ (* x x) (* y y)))))))])
         (hash-ref __dict__ msg))))))

The macro

(define-syntax class
  (syntax-rules (class)
   [(class <class-name> (<attr> ...)
     (method (<method-name> <param> ...) <body>) ...)
      (define (<class-name> <attr> ...)
         (lambda (msg)
            (let* ([__dict__
               (make-immutable-hash
                  (list (cons (quote <attr>) <attr>)
                        ...
                        (cons (quote <method-name>) (lambda (<param> ...) <body>))
                        ...
                        ))])
               (hash-ref __dict__ msg))))]))

Referring calling object

One of the problem that we have not discussed yet is the self / calling object. Currently, our macro does not have the ability to refer the calling “object”.

Suppose the following code

class Point:
   def __init__(self, x, y):
      self.x = x
      self.y = y
   
   def size(self):
      return math.sqrt(self.x ** 2 + self.y ** 2)
   
   def same(self, other):
      return sekf.same() == other.same()

Our current implementation has no trouble implementing the initializer method (it does this automatically), and it can handle simple attribute access of x and y because those identifiers would be bound in the closure returned by the constructor. However, the same poses a problem.

(class Point (x y)
    (method (size) (sqrt (+ (* x x) (* y y))))
    (method (same other) (equal? ??? ((other 'size))))
)

Unlike x and y which are identifiers bind in the closure, the size is a key in the dictionary, we have no way to automatically convert it. Thus, we need an approach that is able to refer the calling object.

In the modern OOP there are two major approaches for doing this.

Using keyword to refer calling object
- (e.g., Java, C++, JS)
Using calling object as method parameter
- (e.g., Python, Rust)

For now, we will look on the second approach.

The simplest way without changing any effort on the macro implementation is making self appear explicitly everywhere. This e.g.,

(class Point (x, y)
    (method (size self) (sqrt (+ (* (self 'x) (* self 'y))
                                 (* (self 'y) (* self 'y)))))
    (method (same self) (equal? ((self 'size) self) ((other 'size) other)))
)

The last line is quite horrible the goal we are expecting is to make (self ‘size) returns a nullary function, so that we can just call it. Nevertheless, what we have here is (self ‘size) returns a unary function that requires to take itself back. This is a silly design, since we are calling using self it is redundant to pass it again.

We will take on how Python deals with this problem. In Python, an instance method call like self.size() automatically binds the value to the left of the period, self, to the first parameter of the method, the arguments in the parentheses get bound to the remaining method parameters.

To address the auto-binding, we will take a look on Python again. In our macro, we store both methods and attributes into a single dictionary in the object. In fact, methods and attributes in Python are stored separately.

The instance methods are stored in the class level
- This can be examined using classname.__dict__
The instance attributes are stored in the object level
- This can be examined using object.__dict__

Based on this we can write out the skeleton of the new macro

(define-syntax class
  (syntax-rules (class)
    [(class <class-name> (<attr> ...)
       (method (<method-name> <params> ...) <body>) ...)
     (begin
        ; Class level dictionary stores the methods
       (define class__dict__
         (make-immutable-hash
          (list (cons (quote <method-name>) (lambda (<params> ...) <body>)) 
                ...))
         )
       (define (<class-name> <attr> ...)
         (let*
            ; Now the object's dict only stores attributes
             ([self__dict__
               (make-immutable-hash
                (list (cons (quote <attr>) <attr>) ...))])
            ; The look up order here is important
            ; It first looks on the object level
            ; Then it looks on the class level
           (lambda (attr)
             (cond
               [(hash-has-key? self__dict__ attr)
                (hash-ref self__dict__ attr)]
               [(hash-has-key? class__dict__ attr)
                (hash-ref class__dict__ attr)])))))]))

Now, we are going to focus on providing a solution for auto-binding.

The auto-binding happens when we extract the method out from class dict, we will apply the calling object into the extracted function and return the new function. Meaning that we should apply the anonymous function back. In this case, we need a way to refer to the object itself and remember that the “object” is the entire lambda expression itself. In other words, this expression needs to be recursive; we can do this by using letrec

(define-syntax class
  (syntax-rules (class)
    [(class <class-name> (<attr> ...)
       (method (<method-name> <params> ...) <body>) ...)
     (begin
       (define class__dict__
         (make-immutable-hash
          (list (cons (quote <method-name>) (lambda (<params> ...) <body>))
                ...))
         )
       (define (<class-name> <attr> ...)
         (letrec
             ([self__dict__
               (make-immutable-hash
                (list (cons (quote <attr>) <attr>) ...))]
           ; Create the recursive binding
           [self (lambda (attr)
             (cond
               [(hash-has-key? self__dict__ attr)
                (hash-ref self__dict__ attr)]
               [(hash-has-key? class__dict__ attr)
                ; Bind self to the first parameter of the method
                ; Return the new funciton
                (lambda args (apply (hash-ref class__dict__ attr) (cons self args)))]))])
           self)))]))

Macro

Review OOP

Adding attributes

Adding methods

Pattern-based macros

Pattern Variables & Literal Keyword

Multiple pattern rules

Text-based vs. AST-based macros

Macro ellipses

Macro for Object

Adding attributes

Adding methods

Referring calling object

CATALOG

FEATURED TAGS