CS150: Problem Set 3: L-System Fractals

Problem Set 3: L-System Fractals - Comments

Question 1: Show that (F O(R-60 F) F) is a string in the language defined by our BNF grammar. To do this, you should start with CommandSequence, and show a sequence of replacements that follow the grammar rules that produce the target string. You can use the rule numbers above to identify the rules.

Start: CommandSequence

By rule 1, rewrite CommandSequence ::= ( CommandList ).

By rule 2, replace the CommandList in ( CommandList ) with Command CommandList to get (Command CommandList ).

For the rest of the steps, we will show the rewriting by identifying the rule we use, and underlining the part of the expression that changes.

Rule 4: (Command CommandList) ==> (F CommandList)
         -------                   - 

Rule 2: (F CommandList) ==> (F Command CommandList)
           -----------

Rule 6: (F Command CommandList ==> (F OCommandSequence CommandList)
           -------                    ----------------

Rule 1: (F OCommandSequence CommandList) ==> (F O(CommandList) CommandList)
            ---------------                      -------------

Rule 2: (F O(CommandList) CommandList) 
             -----------                  
        ==> (F O(Command CommandList) CommandList)
                 -------------------

Rule 5: (F O(Command CommandList) CommandList) 
             -------                             
        ==> (F O(RAngle CommandList) CommandList)
                  ------

Rule 7: (F O(RAngle CommandList) CommandList) 
              -----                               
        ==> (F O(R-60 CommandList) CommandList)
                  ---

Rule 2: (F O(R-60 CommandList) CommandList) 
                  -----------                  
        ==> (F O(R-60 Command CommandList) CommandList)
                      -------------------

Rule 4: (F O(R-60 Command CommandList) CommandList) 
                  -------                
         ==> (F O(R-60 F CommandList) CommandList)
                       -
Rule 3: (F O(R-60 F CommandList) CommandList) 
                     -----------
         ==> (F O(R-60 F) CommandList)

Rule 2: (F O(R-60 F) CommandList) 
                     -----------   
         ==> (F O(R-60 F) Command CommandList)
                          -------------------

Rule 4: (F O(R-60 F) Command CommandList)
                     -------                               
         ==> (F O(R-60 F) F CommandList)
                          _

Rule 3: (F O(R-60 F) F CommandList) ==> (F O(R-60 F) F)
                       -----------

Since we were able to produce (F O(R-60 F) F) from CommandSequence by following the replacement rules, we have shown that (F O(R-60 F) F) is a string in the language.

Question 2: It will be useful to have procedures that take L-system commands as parameters, and return information about those commands. Define the following procedures in ps3.scm:

(is-forward? lcommand) — evaluates to #t if the parameter passed is a forward command (indicated by its first element being a 'f tag).
(is-rotate? lcommand)
(is-offshoot? lcommand)
(get-angle lcommand) — evaluates to the angle associated with a rotate command. Produces an error if the command is not a rotate command (see below for how to produce an error).
(get-offshoot-commands lcommand) — evaluates to the offshoot command list associated with an offshoot command. Produces an error if the command is not an offshoot command.

(define (is-forward? lcommand)
  (eq? (car lcommand) 'f))

(define (is-rotate? lcommand)
  (eq? (car lcommand) 'r))

(define (is-offshoot? lcommand)
  (eq? (car lcommand) 'o))

(define (get-angle lcommand)
  (if (is-rotate? lcommand)
      (cdr lcommand)
      (error "Bad attempt to get angle")))

(define (get-offshoot-commands lcommand)
  (if (is-offshoot? lcommand)
      (cdr lcommand)
      (error "Bad attempt to get offshoot commands")))

Question 3: Demonstrate how any if expression can be rewritten as an equivalent conditional expression. A convincing demonstration would include a transformation similar to the one we showed for transforming a conditional expression into an equivalent if expression, but that transforms an if expression into the equivalent cond expression.

We can transform any if expression:

   (if predicate consequent alternate)

into an equivalent cond expression:

   (cond (predicate consequent)
         (else alternate))

Question 4: Is the begin expression necessary? Either explain how to obtain the same exact behavior as (begin Expr₁ Expr₂) without using begin, or explain why it is not possible to obtain the same behavior using only the subset of Scheme defined in Chapter 3.

The begin expression is not necessary, but it is quite awkward to avoid it. To rewrite a begin expression without using begin, we need to use expressions that evaluate subexpression in a defined order. We have two choices from the basic Scheme expressions: the if expression (since the predicate is always evaluated first, then one of the consequence or alternate), and the application expression (since all the subexpressions are evaluated before the procedure is applied and the body expression of the procedure is evaluated).

Using if expressions we can transform the begin expression (begin Expr₁ Expr₂) into:

   (if (or Expr₁ #t)
       Expr₂
       #f) ;; anything for alternate, since predicate is always true

Using application expressions:

   ((lambda (ignore) Expr₂) Expr₁)

Note that the order is reversed here, since the operaned subexpression will be evaluated before the body expression.

Question 5: Define a procedure rewrite-lcommands in ps3.scm that takes a list of L-system commands as its first parameter. The second parameter is a list of L-system commands that should replace every forward command in the first list of commands in the result.

(define (rewrite-lcommands lcommands replacement)
  (flatten-commands
   (map 
    (lambda (command)  
      (if (is-forward? command)
          replacement ; forwards are replaced with replacement 
          (if (is-offshoot? command) 
              (make-offshoot-command
               (rewrite-lcommands 
                (get-offshoot-commands command) 
                replacement))
              (if (is-rotate? command)
                  command ; rotates are unchanged
                  (error "Bad command: " command)))))
    lcommands)))

Question 6:

Define a procedure, vertical-mid-line that can be passed to draw-curve-points so that (draw-curve-points vertical-mid-line 1000) produces a vertical line in the middle of the window.
Define a procedure, make-vertical-line that takes one parameter and produces a procedure that produces a vertical line at that horizontal location. For example, (draw-curve-points (make-vertical-line 0.5) 1000) should produce a vertical line in the middle of the window and (draw-curve-points (make-vertical-line 0.2) 1000) should produce a vertical line near the left side of the window.

(define vertical-mid-line
  (lambda (t) (make-point 0.5 t)))

(define (make-vertical-line x)
  (lambda (t) (make-point x t)))

Question 7: To check you understand everything so far, define a procedures draw-half-line that uses translate, horiz-line and shrink to draw a line half the width of the window that is centered in the middle of the display window.

(define (draw-half-line)
  (draw-curve-points (translate (shrink horiz-line 0.5) 0.5 0.5) 1000))

Question 8: Define a procedure num-points that determines the approximate number of t-values that will be used for the n^th curve when drawing

   (connect-rigidly c1 (connect-rigidly c2 (connect-rigidly curve3 (... cn))))

(define (num-points p n) 
  (if (= n 0) p (num-points (/ p 2) (- n 1))))

Questions 9 and 10:

(define (convert-lcommands-to-curvelist lcommands)
  (cond ((null? lcommands)
          (list (lambda (t) 
                   (make-colored-point 0.0 0.0 
                                       (make-color 0 255 0)))))
        ((is-forward? (car lcommands))
          (cons-to-curvelist
           (make-vertical-line (get-distance (car lcommands)))
           (convert-lcommands-to-curvelist (cdr lcommands))))
        ((is-rotate? (car lcommands))
               ;;; Rotate every curve in the rest 
         (let
             ;; L-system turns are clockwise, so use - angle
             ((rotate-angle (- (get-angle (car lcommands)))))
           (map
            (lambda (curve)
              (rotate-around-origin curve (get-angle (car lcommands))))
            (convert-lcommands-to-curvelist (cdr lcommands)))))
        ((is-offshoot? (car lcommands))
         (append
          (convert-lcommands-to-curvelist 
           (get-offshoot-commands (car lcommands)))
          (convert-lcommands-to-curvelist
           (cdr lcommands)))
         )
        (#t (error "Bad lcommand!"))))

Question 11: Define a procedure make-lsystem-fractal in ps3.scm that takes three parameters: replace-commands, a list of L-system commands that replace forward commands in the rewriting; start, a list of L-system commands that describes the starting curve; level, the number of iterations to apply the rewrite rule.

(define (make-lsystem-fractal replace-commands start level)
  ((n-times
    (lambda (previous-commands)
      (rewrite-lcommands previous-commands replace-commands))
    level)
   start))

Another possibility without using n-times:

(define (make-lsystem-fractal replace-commands start level)
  (if (= level 0)
      start
      (make-lsystem-fractal replace-commands
                            (rewrite-lcommands start replace-commands)
                            (- level 1))))

Question 12: Submit your best fractal images and the code you used to create them using the fractal submission page. The best pictures will appear on the course web page and will be rewarded with untold fame, invaluable fortune and maybe even a double gold star on this problem set.

Visit the Fractal Gallery at http://www.cs.virginia.edu/cs150/gallery/.