Exam Check-List: Discussion on Part 03 - Functions Part 1

Benutzeravatar
C0RNi666
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 8. Jan 2008 12:51

Exam Check-List: Discussion on Part 03 - Functions Part 1

Beitrag von C0RNi666 »

Hi,

I would also like to participate in the discussion points about possible tasks for the exam. Here is the first part on Functions.

What is a higher order function? What is a first-class function?

What is a higher order function? What is a first-class function?

Higher order functions can take other functions as parameters and/or output functions as well.
A First-Class function are so called first-citizen objects. They can be constructed dynamically during runtime and - just like any other value - they can be passed as arguments to other functions, returned by other functions and stored in data structures.

What is a closure? What information does it contain?

A closure is a representation of a function value. It contains the functions parameters, its body and an environment which holds substitutions to bind free identifiers when applzing the function.

Explain the difference between static scoping and dynamic soping.

With static scoping - or sometimes called lexical scoping -, a name always refers to its local lexical environment. Matching variables only requires the analysis of the static program text and not the dynamic call stack where the variable might be stored at runtime.
By contrast, in dynamic scoping, a variable name's scope is the time-period during which the function is executing: while the function is running, the variable name exists, and is bound to its variable, but after the function returns, the variable name does not exist.

Which of them implements the semantics defined by immediate substitution?
Static scoping implements the semantics defined by immediate substitution, because variables in a static scoping context can be immediately substituted by its values throughout the programm.

Explain the implementation of deferrred substitution. Why is it in general more efficient than immediate substitution?

Deferred substitution means to substitute an expression later, when it is needed or immediately necessary for computation. This makes it more efficient, because possibly ressource hungry computations are not made for substitutions that never occur within the programm flow.

Given a fragment of an interpreter tell whether it implements [static or dynamic scoping / deferred or immediate substitution]. Change it to the other one.

Static scoping and deferred substitution of an interpreter:

Code: Alles auswählen

(define (interp expr fun-defs sub-rep)
  (type-case F1WAE expr
			...
             [with (bound-id named-expr bound-body) 
                   (interp bound-body fun-defs (aSub 
                                                bound-id 
                                                (interp named-expr fun-defs sub-rep)
                                                sub-rep))]
             [app (fun-name arg-expr) 
                  (local ((define the-fun-def (lookup-fundef fun-name fun-defs))) 
                    (interp  (fundef-body the-fun-def) 
                             fun-defs
                             (aSub 
                              (fundef-arg-name the-fun-def) 
                              (interp arg-expr fun-defs sub-rep)
                              (emptySub))))]))

Static scoping and immediate substitution of an interpreter:

Code: Alles auswählen

(define (interp expr fun-defs)
  (type-case F1WAE expr
             [num (n) n]
             [add (l r) (+ (interp l fun-defs) (interp r fun-defs))]
             [sub (l r) (- (interp l  fun-defs) (interp r  fun-defs))]
             [with (bound-id named-expr bound-body) 
                   (interp (subst bound-body bound-id (num (interp named-expr fun-defs))) fun-defs)]
             [id (name) (error "Free identifier")]
             [app (fun-name arg-expr) 
                  (local ([define the-fun (lookup-fundef fun-name fun-defs)]) 
                    (interp (subst 
                             (fundef-body the-fun) 
                             (fundef-arg-name the-fun) 
                             (num (interp arg-expr fun-defs))) fun-defs))]))

Dynamic scoping and immediate substitution of an interpreter:
?

Dynamic scoping and deferred substitution of an interpreter

Code: Alles auswählen

(define (interp expr fun-defs rep)
  (type-case F1WAE expr
             ...
             [with (bound-id named-expr bound-body) 
                   (interp bound-body fun-defs (aSub 
                                                bound-id 
                                                (interp named-expr fun-defs rep)
                                                rep))]
             [app (fun-name arg-expr) 
                  (local ((define the-fun-def (lookup-fundef fun-name fun-defs))) 
                    (interp  (fundef-body the-fun-def) 
                             fun-defs
                             (aSub 
                              (fundef-arg-name the-fun-def) 
                              (interp arg-expr fun-defs rep)
                              rep)))]
			...
			))			
Given a programm, compute the result of avaluating it in languages with static and dynamic scoping, respectively.

Code: Alles auswählen

{with {x 1}
	{with {f {fun {x} {+ x x}}}
		{with {g {fun {y} {+ x y}}}
			{with {x 2}
				{g {f x}}}}}}

Static Scoping: 5
Dynamic Scoping: 6

How are function values represented in an interpreter with deferred substitution? Is it different in an interpreter with immediate substitution?

Yes, the function values are different in these two interpreters. Function values interpreted with deferred substitutions are represented as closures that hold an environment of substitutions to apply in its subexpression.
Function values interpreted with immediate substitutions do not hold this environment, since these substitutions are immediately applied during application.


Some comments on whether my answers are right or wring would be nice, since I am not completely sure whether I have understood everything correctly so far.

Regards,
C0RNi666
Win32: Reboot!
Unix: Be root!

Benutzeravatar
sewe
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von sewe »

Please have a look at static and dynamic scoping in interpreters for FWAE (first-class functions, with, arithmetic expressions) as well. You examples only show F1WAE interpreters. (Corollary: Be aware of the differences.)

Also, as an exercise, try to point out the few places among the (more-or-less) boilerplate code that determine whether something is, for example, dynamically scoped or statically scoped. Being able to spot these key differences in an interpreter quickly might come in handy. ;-)

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: Exam Check-List: Discussion on Part 03 - Functions Part

Beitrag von FeG »

Hi,

first thanks for joining in, this makes one's own solutions more comparable. I'll add some of my solutions/ideas to some of the questions:

3. Explain the difference between static scoping and dynamic scoping. Which of them implements the semantics defined by immediate substitution?
(Just a slightly different definition – as I think the ones on the slides aren't overly precise - on which you, Andreas, might comment..)

Static (or lexical) scoping is scoping based on the syntactial region in the program code, where, e.g., a function definition carries it's definition-time environment with it and is always interpreted in this environment when called later (in a possibly changed environment).

Dynamic scoping is based on the run-time behavior of the program, where, e.g., a function is interpreted in the environment in which it is called (instead of the environment at it's definition time).


5. Given a fragment of an interpreter tell whether it implements [static or dynamic scoping / deferred or immediate substitution]. Change it to the other one.
C0RNi666 hat geschrieben:
Dynamic scoping and immediate substitution of an interpreter:
?
I think these two concepts contradict each other, as with immediate substitution bounded identifiers are directly replaced whereas dynamic scoping is only making an effect when some previously unbounded (or otherwise bounded) identifiers comes in the scope of some other binding and gets "overwritten" by this one.


Additionally now the implementation variants for first-class functions:

FWAE Static vs. Dynamic Scoping / Deferred vs. Immediate Substitution:

Code: Alles auswählen

  (define (interp expr en)
    (type-case FWAE expr
               [with (bound-id named-expr bound-body)
                     (interp bound-body (anEnv bound-id (interp named-expr en) en))]
               [id (v) (lookup v en)]
               [fun (arg body) (closure arg body en)]
               [app (fun-expr arg-value) 
                    (local ([define fun-value (interp fun-expr en)])
                      (interp (closure-body fun-value) 
                              (anEnv (closure-param fun-value) 
                                     (interp arg-value en) 
                                     (closure-env fun-value))))]))
Uses static scoping (as function closure's environment is used for function application) and deferred substitution (as environments are used instead of "subst" calls).

a) Version with Dynamic Scoping and Deferred Substitution:

Code: Alles auswählen

  (define (interp expr en)
    (type-case FWAE expr
               [with (bound-id named-expr bound-body)
                     (interp bound-body (anEnv bound-id (interp named-expr en) en))]
               [id (v) (lookup v en)]
               [fun (arg body) expr]
               [app (fun-expr arg-value) 
                    (local ([define fun-value (interp fun-expr en)])
                      (interp (fun-body fun-value) 
                              (anEnv (fun-param fun-value) 
                                     (interp arg-value en) 
                                     en)))]))
Changed: (1) FWAE expressions are returned instead of FWAE-values, i.e., closure are not used. (2) current environment is used as basis for application's environment instead of stored one in closure.

b) Version with Static Scoping and Immediate Substitution:

Code: Alles auswählen

  (define (interp expr)
    (type-case FWAE expr
               [with (bound-id named-expr bound-body)
                     (interp (subst bound-body bound-id (interp named-expr)))]
               [id (v) (error "Unbound identifier.")]
               [fun (arg body) expr]
               [app (fun-expr arg-value) 
                    (local ([define fun-value (interp fun-expr)])
                      (interp (subst (fun-body fun-value)
                                     (fun-param fun-value) 
                                     (interp arg-value))))]))
Changed: (1) FWAE expressions are returned instead of FWAE-values, i.e., closure are not used. (2) No environments used anymore but instead direct substitution of bindings.


6. Given a fragment of an interpreter that implements [static / dynamic] scoping, find an error and fix it.

F1WAE Interpreter implementing static scoping:

Code: Alles auswählen

  (define (interp expr fun-defs sub-rep)
    (type-case F1WAE expr
      ...
      [with (bound-id named-expr bound-body)
            (interp bound-body fun-defs
                    (aSub bound-id
                          named-expr
                          sub-rep))]
      [id (v) (lookup v sub-rep)]
      [app (fun-name arg-expr)
        (local ([define func (lookup-fundef fun-name fun-defs)])
        (interp (fundef-body func) fun-defs
                (aSub (fundef-arg-name func)
                      (interp arg-expr fun-defs sub-rep)
                      sub-rep)))]))
Errors:
a) In [with ...] clause, aSub has to be built with interpreted value of "named-expr" (since the value is directly returned on id lookup).
b) In [app ...] clause, aSub has to be built with "(emptySub)" as remaining substitution repository, not with "sub-rep".



So far my comments on the first part of the function topic.

Best,
Felix

PS: Maybe you can use ordered lists ([ list=1 ] BBCode) for future posts, I think this eases readability a lot :wink:

Antworten

Zurück zu „Archiv“