[plt-scheme] Re: HtDP 17.7.1 Clarification Requested

From: dave yrueta (dyrueta at gmail.com)
Date: Sat May 24 21:24:12 EDT 2008

After a little further study, I think I arrived at the proper data
definition and the solution to exercise 17.7.3.  Comments are

Here's what I came up with --

; A Scheme Expression (sx) is
; 1. a number (n), or
; 2. a symbol (s), or
; 3. an add-structure (make-add left right) where left and right are
; 4. a mul-structure (make-mul left right) where left and right are sx
; 5. a function-application structure (make-fa nof arg-ex) where nof
is a function name, and arg-exp is a sx

; A Function Definition (fa) is
; a fa-structure (make-def nof nop body)
; where nof(name-of-function) and nop(name-of-parameter) are symbols,
and body is a sx

(define-struct fa(nof arg-exp))
(define-struct fd(nof nop body))

(define d1(make-fd 'f 'x (make-add 3 'x)))
(define d2(make-fd 'g 'x (make-mul 3 'x)))
(define d3(make-fd 'h 'u (make-fa d1 (make-mul 2 'u))))
(define d4(make-fd 'i 'v (make-add(make-mul 'v 'v)(make-mul 'v 'v))))
(define d5(make-fd 'k 'w (make-mul(make-fa d3 'w)(make-fa d4 'w))))

;;evaluate-with-one-def: sx P > error or Scheme Expression
;;consumes a Scheme Expression and a Function Definition, and returns
either an 'error or the evaluated Scheme Expression
(define(evaluate-with-one-def sx P)
    [(numeric? sx)
       [(number? sx)(evaluate-expression(subs(fd-nop P)sx(fd-body
       [else(evaluate-with-one-def (evaluate-expression sx)P)])]
    [else 'error]))

;;subst:symbol number scheme-expression > scheme-expression
;;consumes a symbol, number and scheme-expression, substitutes all
instances of the symbol appearing in the scheme-expression with the
number, and then returns a structurally equivalent expression.
(define(subs sym num sx)
    [(mul? sx)(make-mul (subs sym num (mul-left sx))(subs sym num (mul-
right sx)))]
    [(add? sx)(make-add (subs sym num (add-left sx))(subs sym num (add-
right sx)))]
    [(fa? sx) (evaluate-with-one-def(subs sym num (fa-arg-exp sx))(fa-
nof sx))]
    [(number? sx)sx]
    [(symbol=? sym sx)num]
    [else sx]))

(define(numeric? sx)
    [(number? sx)true]
    [(struct? sx)(test-struc sx)]
    [else false]))

(define(test-struc sx)
    [(mul? sx)(and(numeric? (mul-left sx))(numeric? (mul-right sx)))]
    [else (and(numeric? (add-left sx))(numeric? (add-right sx)))]))

(define(evaluate-expression nx)
    [(boolean=? (numeric? nx)false)'error]
    [else (process-nx nx)]))

(define(process-nx nx)
    [(number? nx)nx]
    [(mul? nx)(*(evaluate-expression (mul-left nx))(evaluate-
expression (mul-right nx)))]
    [else (+(evaluate-expression (add-left nx))(evaluate-expression
(add-right nx)))]))

On May 24, 2:26 pm, dave yrueta <dyru... at gmail.com> wrote:
> Hi All --
> Can someone clarify the meaning of HtDP problems 17.7.1 and 17.7.2?
> 17.7.1 --“…represent the application of a user-defined function to an
> expression such as (f ( + 1 1)) or (* 3 (g 2)).  The application
> should be represented as a structure with two fields. The first field
> contains the name of the function, the second one the representation
> of the argument expression.”
> So, if a Function Application (fa) structure is defined as --
>                 (make-fa nof arg-exp)
> -- where nof is the name-of-the-function, and arg-exp is some Scheme
> Expression(sx, defined below), what is meant by ‘the name of the
> function’?
> For example, when considering (f (+ 1 1)) above, if f is equivalent to
> --
> (define(f x)
>         (+ x 3))
> -- then is the ‘name of the function’
>         1. ‘f (a symbol)
>         2. (define f (make-add ‘x 3)), or
>         3.  something else?
> Similarly, exercise 17.7.2 asks for a Function Definition (fd)
> structure, which includes the function name, a single parameter name,
> and the body--
>                 (make-fd nof nop body)
> --where nof and nop are symbols and the body is some Scheme Expression
> (sx).
> Hence, when applied to a Function Definition structure, (define(f x(+
> 3 x)) would become --
> (make-struct ‘f ‘x (make-add 3 ‘x))).
> But what about a function which references f, such as
> (define(h u)(f(* 2 u))?
> If the Function Application structure is used here to replace (f(* 2
> u)), how is the attribute for ‘name of the function’ defined?
> 1.      As a Function Definition (fd) structure (define f (make-struct ‘f
> ‘x (make-add 3 ‘x)))?
> 2.      Some other Scheme Expression (sx) , such as ‘f, or (define f(make-
> add 3 ‘x))?
> This problem builds on the data definition for Scheme Expressions (sx)
> in exercise 14.4.1, which I defined as follows:
>         A Scheme Expression (sx) is
> 1.      a number (n)
> 2.      a symbol (s)
> 3.      a structure for primitive ‘+ (make-add sx sx)
> 4.      a structure for primitive ‘* (make-mul sx sx)
> Thanks,
> Dave Yrueta
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.