Scheme code understanding

Dev Shed Forums Sponsor:

March 21st, 2012, 10:41 AM

ansin

Registered User

Join Date: Mar 2012

Posts: 3

Time spent in forums: 49 m 47 sec
Reputation Power: 0

Other Language - Scheme code understanding

(define (reduce f)
((lambda (value) (if (equal? value f) f (reduce value)))
(let r ((f f) (g ()))
(cond ((not (pair? f))
(if (null? g) f (if (eq? f (car g)) (cadr g) (r f (caddr g)))))
((and (pair? (car f)) (= 2 (length f)) (eq? 'lambda (caar f)))
(r (caddar f) (list (cadar f) (r (cadr f) g) g)))
((and (not (null? g)) (= 3 (length f)) (eq? 'lambda (car f)))
(cons 'lambda (r (cdr f) (list (cadr f) (delay (cadr f)) g))))
(else (map (lambda (x) (r x g)) f))))))

; (reduce '((lambda x x) 3)) ==> 3
; (reduce '((lambda x (x x)) (lambda x (lambda y (x y)))))
; ==> (lambda #[promise 2] (lambda #[promise 3] (#[promise 2] #[promise 3])))

; Comments: f is the form to be evaluated, and g is the local assignment
; function; g has the structure (variable value g2), where g2 contains
; the rest of the assignments. The named let function r executes one
; pass through a form. The arguments to r are a form f, and an
; assignment function g. Line 2: continue to process the form until
; there are no more conversions left. Line 4 (substitution): If f is
; atomic [or if it is a promise], check to see if matches any variable
; in g and if so replace it with the new value. Line 6 (beta
; reduction): if f has the form ((lambda variable body) argument), it is
; a lambda form being applied to an argument, so perform lambda
; conversion. Remember to evaluate the argument too! Line 8 (alpha
; reduction): if f has the form (lambda variable body), replace the
; variable and its free occurences in the body with a unique object to
; prevent accidental variable collision. [In this implementation a
; unique object is constructed by building a promise. Note that the
; identity of the original variable can be recovered if you ever care by
; forcing the promise.] Line 10: recurse down the subparts of f.
I'm playing around with Scheme trying to decipher it's syntax, and i need some help with the above code. Yes, the comments are pretty much covering it but i can't seem to understand the pieces of it. For example can someone extract from the "reduce" function the part that does the alpha conversion , create a separate function for it and call it inside "reduce" ?. Also it says that i can retrieve the value of the promise by forcing it, where exactly in the code should i add the force function ? And instead of forcing the old variable i want to generate a new one with gensym so probably something like (gensym (force promise)) but where to add it.

March 21st, 2012, 05:07 PM

OmegaZero

Contributing User

Join Date: May 2007

Posts: 737

Time spent in forums: 3 Weeks 5 Days 8 m 19 sec
Reputation Power: 928

(Note: In the future, place [code][/code] tags around source code to keep it legible)

If your goal is to learn Scheme, I'd suggest putting this code aside (and avoiding anything from the same source for that matter). I'm not a big fan of Scheme, so I can't suggest any good resources off hand. You might find the (free) book Structure and Interpretation of Computer Programs helpful--the primary topic is computer science in general, but it teaches the basics of Scheme in the process.

If you're invested in this code, I can straighten out the code a bit for you, but I think you'll just end up with an even more confusing mess once you start seeing what that code is actually doing.

__________________
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);

March 22nd, 2012, 09:01 AM

ansin

Registered User

Join Date: Mar 2012

Posts: 3

Time spent in forums: 49 m 47 sec
Reputation Power: 0

well sure, i would appreciate if you would , this was a old task i had (extra credit) which i didn't manage to resolve in the nick of time , but hey , better later than never. I'll wait for your response , thank you

March 22nd, 2012, 07:18 PM

OmegaZero

Contributing User

Join Date: May 2007

Posts: 737

Time spent in forums: 3 Weeks 5 Days 8 m 19 sec
Reputation Power: 928

Here are the code & comments reformatted to be legible and half-way sane. Good luck.

Code:

(define (reduce expression)
  (
    ; Be cute and avoid an additional
    ; let or define by taking the result
    ; of the next expression as an argument
    (lambda (reduced-expression)
      ; Was there nothing to reduce?
      (if (equal? reduced-expression expression)
        ; Then return the final result
        expression
        ; Otherwise try reducing it further
        (reduce reduced-expression)
      )
    )
    (let reduce-step
      (
        (expression expression)
        (symbols ())
      )
      (cond
        ; Is the expression a single token?
        ( (not (pair? expression))
          (if (null? symbols)
            ; No symbols can be resolved
            expression
            ; Is the token the first entryin symbols
            (if (eq? expression (car symbols))
              ; Yes, substitute it
              (cadr symbols)
              ; No, recurse with the remaining symbol table entries
              ; (it would just be boring to implement a lookup function)
              (reduce-step expression (caddr symbols))
            )
          )
        )
        ; A function application of the form
        ; ( (lambda ...) argument )
        ( (and
            (pair? (car expression))
            (= 2 (length expression))
            (eq? 'lambda (caar expression))
          )
          ; Reduce the lambda body
          (reduce-step
            (caddar expression)
            ; Evaluating its argument 
            ; and adding it to the symbol table
            (list (cadar expression)
                  (reduce-step (cadr expression) symbols)
                  symbols
            )
          )
        )
        ; A function definition of the form
        ; (lambda argument body)
        ( (and
            (not (null? symbols))
            (= 3 (length expression))
            (eq? 'lambda (car expression))
          )
          ; Resolve any symbols bound by enclosing lambdas
          ; Using a placeholder for the symbol bound by this
          ; lambda
          (cons 'lambda
                (reduce-step (cdr expression)
                  (list (cadr expression)
                        (delay (cadr expression))
                        symbols)
                )
          )
        )
        ; Otherwise, perform substitutions in this expression
        ; from the symbol table
        (else
          (map (lambda (x) (reduce-step x symbols)) expression)
        )
      )
    )
  ) 
)

March 23rd, 2012, 04:07 AM

ansin

Registered User

Join Date: Mar 2012

Posts: 3

Time spent in forums: 49 m 47 sec
Reputation Power: 0

You sir, are a life saver ,thank you this is so much better now. Though i would still like to ask you this, let's take this expression as an example :

Code:

(reduce '((lambda p (p (lambda x (lambda y x)))) (((lambda x (lambda y (lambda z ((z x) y)))) (lambda y (lambda x (y x)))) (lambda z (lambda x (lambda y x))))))

. With a force added in this line

Code:

 ; Yes, substitute it
              (cadr symbols)

my output is this

Code:

(lambda y (lambda x (y x)))

and i want it to be something like this :

Code:

(lambda g10592 (lambda x (g10592 x)))

So instead of using the old value (from when i delay it , i want to generate a new symbol).Also , what exactly would the lookup function do, maybe i will give it a go.

LE: What is the meaning of () in this piece of code

Code:

(let reduce-step
      (
        (expression expression)
        (symbols ())

, because i get an empty application error , can i replace the () with something else ? (I replaced it with gensym and it gets rid of the error and the output is the same) ...so what's the deal with that ? Thank you again

March 23rd, 2012, 09:35 PM

OmegaZero

Contributing User

Join Date: May 2007

Posts: 737

Time spent in forums: 3 Weeks 5 Days 8 m 19 sec
Reputation Power: 928

Quote:

Originally Posted by ansin

So instead of using the old value (from when i delay it , i want to generate a new symbol).

You've pretty much said it there--instead of the delayed old-value generate a new symbol.

Quote:

Originally Posted by ansin

Also , what exactly would the lookup function do, maybe i will give it a go.

If I were writing this, I would have written helper functions to handle operations on the symbol table. The expression-reducing code wouldn't need to know about the internal representation of the symbol table then, and would be less cluttered and more self-documenting as a result. They would look something like:

Code:

(define (new-symbol-table) ...)
(define (define-symbol symbol-table symbol value) ... )
(define (lookup-symbol symbol-table symbol) ...)

You might even be able to drop those symbol-table arguments--I don't recall if Scheme permits nested declarations.

Quote:

Originally Posted by ansin

LE: What is the meaning of () in this piece of code

It's the empty list. Maybe '() or Nil is how your LISP dialect spells it.

October 10th, 2012, 03:33 AM

dfhvghew

Registered User

Join Date: Oct 2012

Posts: 1

Time spent in forums: 8 m 47 sec
Reputation Power: 0

You sir

You sir, are a life saver ,thank you this is so much better now. Though i would still like to ask you this, let's take this expression as an example :

Other Language - Scheme code understanding

Developer Shed Advertisers and Affiliates