Exam Check-List: Discussion on Part 06 - Recursion

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

Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von FeG »

Hi,

thank God the question lists are getting shorter :wink: ... below my solution to the sixth topic of the exam check-list (-> spoiler alert...).

(I only have a question on question 2, see below...)

Best,
Felix


  1. Name 3 different ways to implement recursion.
    • global function declarations
    • cyclically bound environments
    • use recursion of underlying, interpreting language (meta-interpretation)
    • [Y/fix-point combinator]
    • [dynamic scoping]
  2. Explain the strategy of implementing recursion by means of [global function declarations/lazy evaluation/immediate substitution/dynamic scoping/cyclic environments/meta-interpretation]
    • global function declarations: The interpreter is passed a list of function definitions, seperately to the program. Function calls are resolved by looking the function up in the list, thus function calls can be recursive.
    • lazy evaluation: ?
    • immediate substitution: ?
    • dynamic scoping: The function expression is bound (e.g., in a with clause) as-is to the function name, i.e., especially not enclosed in a closure, and does not carry the definition-time environment with it. So, when later applied, it can be dynamically scoped in an environment, where the original binding of the function is in effect, thus providing a function definition that can be recursively called.
    • cyclic environments: One closes the (function closure) environment over itself, i.e., set "env = (addEntry f (fclosure param body env) oldEnv)", using mutable data structures.
    • meta-interpretation: Use recursion of the interpreting language to implement recursion, e.g., implement environments using scheme functions, which allow recursion and thus allow recursive calls to environments to implement recursion in the interpreted language.
    --> I don't see how lazy evaluation/immediate substitution alone can be used to implement recursion. Can someone enlight me?
  3. Find error in a fragment of interpreter implementing recursion by means of [cyclic environments/immediate substitution] and fix it.

    Code: Alles auswählen

    (define (interp expr en)
      (type-case RCFAE expr
                 ...
                 [fun (arg body) (closure arg body en)]
                 [rec (bound-id named-expr bound-body)
                   (interp bound-body
                           (local
                             ([define value-holder (box (numb 746))]
                              [define new-env (recEnv bound-id value-holder en)]
                              [define named-expr-val (interp named-expr en)])
                             (begin
                               (set-box! value-holder named-expr-val)
                               value-holder)))]
                 ...))
    
    Correct version:

    Code: Alles auswählen

    (define (interp expr en)
      (type-case RCFAE expr
                 ...
                 [fun (arg body) (closure arg body en)]
                 [rec (bound-id named-expr bound-body)
                   (interp bound-body
                           (local
                             ([define value-holder (box (numb 746))]
                              [define new-env (recEnv bound-id value-holder en)]
                              [define named-expr-val (interp named-expr new-env)])
                             (begin
                               (set-box! value-holder named-expr-val)
                               new-env)))]
                 ...))
    
    a) [define named-expr-val (interp named-expr en)] has to be [define named-expr-val (interp named-expr new-env)] --- the whole point is to evaluate the named-expr in the new environment (which at this point just has a dummy value for the recursive call, which however is only evaluated to a closure).
    b) The last value, being returned, has to be the new environment new-env instead of value-holder.


    4. Describe the environment at certain points of evaluating the given program, assuming an interpreter using cyclic environments to implement recursion.

    Code: Alles auswählen

    {with {x 2}
      {rec {f {fun {y} {if0 y 0 {+ x {f {- y 1}}}}}}
           {f 3}}}
    
    At the point directly before evaluating "{f 3}", the environment is

    Code: Alles auswählen

      env = (
        f -> (closure 'y
                      (if0 (id 'y) (num 0) (add (id 'x) (app (id 'f) (sub (id 'y) (num 1)))))
                      env),
        x -> (numb 2)
      )
    
    Note that env is cyclically bound in the closure bound to f.
Zuletzt geändert von FeG am 23. Aug 2012 13:51, insgesamt 1-mal geändert.

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

Re: Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von sewe »

FeG hat geschrieben:
  1. Name 3 different ways to implement recursion.
    • global function declarations
    • cyclically bound environments
    • use recursion of underlying, interpreting language (meta-interpretation)
    • [Y/fix-point combinator]
There is also a fifth way: dynamic scoping. (If you don't believe me, try it out with the interpreter at https://cage.st.informatik.tu-darmstadt ... coping.rkt.

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

Re: Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von FeG »

sewe hat geschrieben:There is also a fifth way: dynamic scoping. (If you don't believe me, try it out with the interpreter at https://cage.st.informatik.tu-darmstadt ... coping.rkt.
Nice, I didn't saw that... I added the explanation in the first post.

For lazy evaluation and immediate substitution I however still only see a way to implement this using somethink like cyclic environments.

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

Re: Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von sewe »

FeG hat geschrieben: For lazy evaluation and immediate substitution I however still only see a way to implement this using somethink like cyclic environments.
If you don't believe that immediate substitution works, give https://cage.st.informatik.tu-darmstadt ... -subst.rkt a try.

But where did you find the statement that lazy evaluation works for this?

sqrtsben
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 17. Sep 2010 15:46

Re: Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von sqrtsben »

To quote the slides:
Explain the strategy of implementing recursion by means of [global function declarations/lazy evaluation/immediate substitution/dynamic scoping/cyclic environments/meta-interpretation]

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

Re: Exam Check-List: Discussion on Part 06 - Recursion

Beitrag von FeG »

sewe hat geschrieben:But where did you find the statement that lazy evaluation works for this?
As sqrtsben wrote, see question 2 in this part.

Antworten

Zurück zu „Archiv“