#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2012
    Posts
    3
    Rep Power
    0

    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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    (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);
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2012
    Posts
    3
    Rep 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
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    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)
            )
          )
        )
      ) 
    )
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2012
    Posts
    3
    Rep 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
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    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.

    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.


    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.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    1
    Rep 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 :

IMN logo majestic logo threadwatch logo seochat tools logo