March 21st, 2012, 11:41 AM

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, 06:07 PM

(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 helpfulthe 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, 10:01 AM

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, 08:18 PM

Here are the code & comments reformatted to be legible and halfway 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 (reducedexpression)
; Was there nothing to reduce?
(if (equal? reducedexpression expression)
; Then return the final result
expression
; Otherwise try reducing it further
(reduce reducedexpression)
)
)
(let reducestep
(
(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)
(reducestep 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
(reducestep
(caddar expression)
; Evaluating its argument
; and adding it to the symbol table
(list (cadar expression)
(reducestep (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
(reducestep (cdr expression)
(list (cadr expression)
(delay (cadr expression))
symbols)
)
)
)
; Otherwise, perform substitutions in this expression
; from the symbol table
(else
(map (lambda (x) (reducestep x symbols)) expression)
)
)
)
)
)
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}>(\&Meh);
March 23rd, 2012, 05:07 AM

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 reducestep
(
(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, 10:35 PM

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 thereinstead of the delayed oldvalue 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 expressionreducing code wouldn't need to know about the internal representation of the symbol table then, and would be less cluttered and more selfdocumenting as a result. They would look something like:
Code:
(define (newsymboltable) ...)
(define (definesymbol symboltable symbol value) ... )
(define (lookupsymbol symboltable symbol) ...)
You might even be able to drop those symboltable argumentsI 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);
October 10th, 2012, 04:33 AM

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 :