Functions and scope

Thus far, we can construct expressions (type PicExprC) in our “PicLang” and run them through our interpreter (we’ll indulge a bit and also refer to it as a “picture synthesizer”) to produce a “picture” which we can “render” to a P3 format PPM file for viewing.

When producing pictures using our synthesizer, as our compositions grow in complexity, we’re bound to come across repeated patterns that we will wish we didn’t have to repeat ourselves about. Functions are about that, and adding functions to our language will vastly increase the breadth of what we can accomplish within it.

Defining functions

Towards this, we’ll consider a function definition structure that captures the essence of a general enough function within our language.

(struct FunDefC ([name : Symbol]
                 [arg : Symbol]
                 [expr : PicExprC]))

The above is in #lang typed/racket, but we can write it simpler in normal #lang racket like this -

(struct FunDefC (name arg expr))

This structure captures what we need to specify a function. We’ll identify a function by its name, we’ll identify its argument (a.k.a. “formal parameter”) using a symbol and we’ll give a PicExprC expression as the body of the function. In other words, we’re interested in functions that compute pictures (via the interpreter).

When we call such a function, what kind of value should we pass for the argument? We have a couple of choices given our picture language terms. We could make functions of type Number -> Picture or Picture -> Picture. [1]

In our language so far, only the picture parts of our expressions can be other expressions. The numbers are all expected to be constants – for example: (RotateS 30.0 (TranslateS 3 4 (SquareS 15.0))). We don’t have the means to provide expressions in place of numbers so far. So we’ll limit our discussion to functions which take a Picture as an argument and produce a Picture as a result.

Let’s look at an example function definition for a function that encapsulates the “translate and colourize” operation. To keep the discussion simple, we’ll assume that all terms are part of our core language. You should be able to determine which ones are better expressed using a “surface syntax” versus “core” split and apply desugar in the appropriate places to complete the picture.

(FunDefC 'trans-and-colorize 'p (ColorizeC red (TranslateC 2.0 3.0 <a-reference-to-p>)))

We have a gap in our language here. We need to be able to express the idea of “use whatever value this identifier called 'p stands for in this slot” in order to be able to write function definitions in the first place. Towards this, we’ll add a new term to our PicExprC type with the following structure –

(struct IdC ([id : Symbol]))

Now we can express the above function definition as –

(FunDefC 'trans-and-colorize 'p (ColorizeC red (TranslateC 2.0 3.0 (IdC 'p))))

Whenever we’re repeating ourselves, we need to be careful and examine what would happen if we made some errors. For example, what if we’d written the above function definition like this instead? –

(FunDefC 'trans-and-colorize 'p (ColorizeC red (TranslateC 2.0 3.0 (IdC 'q))))

This definition has no meaning for us, since the identifier 'q has no definition within any evaluation context. Such a variable that is not “declared” as a formal parameter in the function definition and still finds mention in the function definition’s body is called a “free variable”. In our language so far, we do not ascribe any meaning to such “free variables” and therefore consider such an expression to be an error.

Applying functions: substitution a.k.a. β-reduction

Ok, we have a function definition now. How do we then use it to make pictures? We need a way to “apply” the function to a concrete picture expression value to compute the required result. We therefore need yet another addition to our language to express this concept of “function application”.

(struct ApplyC ([fn : Symbol] [arg : PicExprC]))

Given that we’re identifying functions by name, we can express an application by giving the function name we wish to use and provide a value to be use as argument. Note that there is a design choice we can make here since we’re using names to denote functions as well as placeholder slots in expressions that need to be filled with values –

  1. We can permit a “formal parameter” name to be the same that of another function since we’re not permitting IdC references to be used for the fn part of our ApplyC structure. So here, we’re keeping function names and value identifiers in separate “namespaces”. Some languages like Common Lisp take this route.

  2. If we permit FunDefC itself to be a valid PicExprC and which can be passed as an argument, we can extend our ApplyC to accept such a function specification in its fn slot. This way, we have “first class functions” in our language, which makes a language expressive.

We’ll start with (1) to keep the discussion simple before we take a stab at (2).

So what should our interpreter do when it encounters an ApplyC term?

(define (interp picexprC fundefs)
    (match picexprC
        ; ...
        [(ApplyC fn arg)
         ; ... what should go here? ...
        ]
        ; ...))

First off, we need a function to lookup the named function in the supplied list of function definitions.

(define (lookup-fundef name fundefs)
    (if (empty? fundefs)
        (raise-argument-error 'lookup-fundef
                              (string-append "Definition for function named " name)
                              name)

        (if (equal? name (FunDefC-name (first fundefs)))
            (first fundefs)
            (lookup-fundef name (rest fundefs)))))

Given this, we need a procedure by which we can perform “β-reduction” on the function’s definition expression, using the arg part of the ApplyC term.

(define (subst value for-identifier in-picexpr)
    (match in-picexpr
        ; examine each possible term and determine
        ; how to substitute the value for the
        ; identifier slots used in the expression.))

For one thing, we subst needs to deal with the new IdC term. So we need a match arm like this -

[(IdC id) (if (equal? for-identifier id)
              value
              (error "Unknown identifier"))]

What about something like TranslateC? For a term like TranslateC, the expectation is that subst will produce the same TranslateC as the result but with any identifiers in the expression part of TranslateC substituted with the given value.

[(TranslateC dx dy picexprC)
 (TranslateC dx dy (subst value for-identifier picexprC))]
[(OverlayC pic1 pic2)
 (OverlayC (subst value for-identifier pic1)
           (subst value for-identifier pic2))]
; .. and so on

Even ApplyC follows the same structure within subst –

[(ApplyC fname picexprC)
 (ApplyC fname (subst value for-identifier picexprC))]

Within our interp though, we will make use of subst to perform a “β-reduction”.

(define (interp picexprC fndefs)
    (match picexprC
        ;...
        [(ApplyC fname valexprC)
         (let ([def (lookup-fundef fname fundefs)])
            (subst valexprC (FunDefC-arg def) (FunDefC-expr def)))]
        ;...
        ))

… but that’s actually of the wrong type since subst produces a PicExprC as its result but interp is of type PicExprC -> Picture. So we need to run the interpreter on the expression produced by subst like this –

(define (interp picexprC fndefs)
    (match picexprC
        ;...
        [(ApplyC fname valexprC)
         (let ([def (lookup-fundef fname fundefs)])
            (interp (subst valexprC (FunDefC-arg def) (FunDefC-expr def))))]
        ;...
        ))

Two evaluation modes

Consider the function definition below –

(FunDefC 'ghost 'p (OverlayC (IdC 'p') (TranslateC 4.0 (OpacityC 0.5 (IdC 'p')))))

The identifier 'p appears twice in this. If we then apply this function to (RotateC 30 (SquareC 5.0)), we will get this as the result –

(OverlayC (RotateC 30 (SquareC 5.0))
          (TranslateC 4.0 (Opacity 0.5 (RotateC 30 (SquareC 5.0)))))

Note the repeated occurrence of the (RotateC...) sub-expression. So what we have here in our interpreter is a way of calculating that puts off the actual evaluation of the expression when it is actually required. Even there, it performs redundant calculation of the same picture. This “putting off until required” strategy is what is called “lazy evaluation” – though the expression if repeated in multiple slots is not repeatedly evaluated in lazy languages.

Exercise

Modify the interpreter so that it still performs lazy evaluation, but does not perform redundant calculations when the expression is substituted in multiple places inside the function body.

In contrast, we can choose to first evaluate the picture-expression given in the ApplyC term before we pass it on to subst to perform substitution. i.e. we have –

(define (interp picexprC fndefs)
    (match picexprC
        ;...
        [(ApplyC fname valexprC)
         (let ([def (lookup-fundef fname fundefs)])
            (interp (subst (interp valexprC) (FunDefC-arg def) (FunDefC-expr def))))]
        ;...
        ))

Note

There is a problem with this. Can you spot it before you read on?

The problem is that our language does not yet admit any way to specify an “already computed picture” – i.e. a “literal picture”. You can see this by looking at the result type of (interp valexprC) which should be a Picture, but subst internally returns this Picture value in this case instead of a PicExprC as we wanted.

The solution is to add a term to our PicExprC type that wraps or “tags” such a value.

(struct PictureC ([pic : Picture]))

Now, we can write the “eager interpreter” as –

(define (interp picexprC fndefs)
    (match picexprC
        ;...
        [(PictureC pic) pic]
        [(ApplyC fname valexprC)
         (let ([def (lookup-fundef fname fundefs)])
            (interp (subst (PictureC (interp valexprC)) (FunDefC-arg def) (FunDefC-expr def))))]
        ;...
        ))

It is cheap for our interpreter to “evaluate” a PictureC term since there is nothing that it really needs to do beyond return the provided value, as seen above.

Scope

So far, we’ve only seen only one condition that indicates we have a problematic function definition at hand – whenever we find a “free variable” in the expression of a function definition, such an expression cannot be interpreted.

To see why it cannot be interpreted, look at what the IdC arm of our interpreter’s match expression should do –

(define (interp picexprC fndefs)
    (match picexprC
        ;...
        [(IdC id) <what-to-do-here?>]
        ;...
        ))

Since the job of subst is to get rid of all occurrences of IdC terms in its result, the interpreter should never see an IdC term! So the only response it can have to this is to raise an error – using (raise-argument-error 'interp "No free variables" picexprC).

However, intuitively, we expect the interpreter to “lookup” the meaning of the identifier somewhere to determine what it is and use what it finds. This is the next notion we’ll discuss - that of “environments and scope”.