Ok, to me Scheme is fun.  Why? Because could you can do things like this quite easily…

[From my CS342 Spring Semester 2003 Second Midterm]

Consider the following BNF-specification:

<boolean-expression> ::= true

|   false

|   not <boolean-expression>

|   and <boolean-expression> <boolean-expression>

|   or <boolean-expression> <boolean-expression>

|   ( <boolean-expression> )

Question #1 – Define it’s abstract syntax:


(define-datatype boolean-expression boolean-expression?
                (bool-not  (bool-exp boolean-expression?))
                (bool-and  (bool-exp1 boolean-expression?) (bool-exp2 boolean-expression?))
                (bool-or   (bool-exp1 boolean-expression?) (bool-exp2 boolean-expression?))
                (bool-item (b-item boolean-expression?))
 ) ; end define-datatype

Question #2 – Define the scanner and the parser specs using the SLLGEN format:


(define bool-exp-scanner
    '( (white-sp  (whitespace)  skip) )

(define bool-exp-grammar
    '( (boolean-expression ("true")  bool-true)
       (boolean-expression ("false") bool-false)
       (boolean-expression ("not" boolean-expression) bool-not)
       (boolean-expression ("(" boolean-expression ")") bool-item)
       (boolean-expression ("and" boolean-expression boolean-expression) bool-and)
       (boolean-expression ("or" boolean-expression boolean-expression) bool-or)

Question #3 – Define a fron-end:


(define front-end (sllgen:make-string-parser bool-exp-scanner bool-exp-grammar))

Question #4 – Define an interpreter, called boolean-interpreter that when applied to a string returns its corresponding Scheme truth value:

> (boolean-interpreter "or (true) and or true (not false) false")
# f


(define boolean-interpreter
  (lambda (bstr)
    (let ((exp (front-end bstr)))
	   (if (boolean-expression? exp)
                (bool-interpreter-helper exp)
                (eopl:error 'boolean-interpreter "Invalid boolean expression ~s" exp)

(define bool-interpreter-helper
  (lambda (exp)
      (cases boolean-expression exp
          (bool-true () #t)
          (bool-false () #f)
          (bool-not (not-exp) (not (bool-interpreter-helper not-exp)))
          (bool-and (exp1 exp2) (and (bool-interpreter-helper exp1) (bool-interpreter-helper exp2)))
          (bool-or (exp1 exp2) (or (bool-interpreter-helper exp1) (bool-interpreter-helper exp2)))
          (bool-item (b) (boolean-interpreter-helper b))

A simple (interpreted) boolean programming language! Pretty sweet, huh?