A self-applicable syntax checker for a subset of Scheme

This chapter describes the midterm project: a self-applicable syntax checker for an extended subset of Scheme.

Resources

• The Scheme code to get you started with your syntax checker (latest version: 12 Oct 2025).

Reminder about directories

The Chez Scheme procedure cd, when used with no arguments, yields a string that represent the path of the directory in which the current instance of Chez Scheme runs.

Given a string that represents the path of the directory in which we would like the current instance of Chez Scheme to run, applying the Chez Scheme procedure cd to this string changes the directory in which the current instance of Chez Scheme runs.

For example, suppose that Chez Scheme was started in the directory denoted by /foo/bar. Then evaluating (cd) yields "/foo/bar". Suppose further that you want to change this directory to /foo/bar/baz. This change can be achieved either by changing the current directory to the absolute path /foo/bar/baz or by changing the current directory to the relative path bar. In other words, evaluating either of (cd "/foo/bar/baz") or of (cd "baz") will achieve this change.

The project: a self-applicable syntax checker

The goal of this midterm project is

1. to implement predicates and accessors of the BNF (there is no need for the constructors: Scheme constructs are written directly);
2. to program a syntax checker that is self-applicable and that does not crash, diverge, or raise errors.

Here is the operationalized BNF:

<program>            ::= <toplevel-forms>

<toplevel-forms>     ::= ()
                       | (<toplevel-form> . <toplevel-forms>)

<toplevel-form>      ::= <definition>
                       | <expression>

<definition>         ::= (define <variable> <expression>)

<expressions>        ::= ()
                       | (<expression> . <expressions>)

<expression>         ::= <number>
                       | <boolean>
                       | <character>
                       | <string>
                       | <variable>
                       | <time-expression>
                       | <if-expression>
                       | <and-expression>
                       | <or-expression>
                       | <cond-expression>
                       | <case-expression>
                       | <let-expression>
                       | <letstar-expression>
                       | <letrec-expression>
                       | <begin-expression>
                       | <unless-expression>
                       | <quote-expression>
                       | <lambda-abstraction>
                       | <application>

<time-expression>    ::= (time <expression>)

<if-expression>      ::= (if <expression> <expression> <expression>)

<and-expression>     ::= (and . <expressions>)

<or-expression>      ::= (or . <expressions>)

<cond-expression>    ::= (cond . <cond-clauses>)

<cond-clauses>       ::= (<else-clause>)
                       | (<cond-clause> . <cond-clauses>)

<else-clause>        ::= [else <expression>]

<cond-clause>        ::= [<expression>]
                       | [<expression> <expression>]
                       | [<expression> => <expression>]

<case-expression>    ::= (case <expression> . <case-clauses>)

<case-clauses>       ::= (<else-clause>)
                       | (<case-clause> . <case-clauses>)

<case-clause>        ::= [<quotations> <expression>]

<quotations>         ::= ()
                       | (<quotation> . <quotations>)

<let-expression>     ::= (let <let-bindings> <expression>)
                         ;;; where all the variables declared in the let-bindings are distinct

<let-bindings>       ::= ()
                       | (<let-binding> . <let-bindings>)

<let-binding>        ::= [<variable> <expression>]

<letstar-expression> ::= (let* <letstar-bindings> <expression>)

<letstar-bindings>   ::= ()
                       | (<letstar-binding> . <letstar-bindings>)

<letstar-binding>    ::= [<variable> <expression>]

<letrec-expression>  ::= (letrec <letrec-bindings> <expression>)
                         ;;; where all the variables declared in the letrec-bindings are distinct

<letrec-bindings>    ::= ()
                       | (<letrec-binding> . <letrec-bindings>)

<letrec-binding>     ::= [<variable> <lambda-abstraction>]

<begin-expression>   ::= (begin <expression> . <expressions>)

<unless-expression>  ::= (unless <expression> <expression>)

<quote-expression>   ::= (quote <quotation>)

<quotation>          ::= <number>
                       | <boolean>
                       | <character>
                       | <string>
                       | <symbol>
                       | ()
                       | (<quotation> . <quotation>)

<lambda-abstraction> ::= (lambda <lambda-formals> <expression>)
                       | (trace-lambda <variable> <lambda-formals> <expression>)
                         ;;; where the formals are a list (proper or improper) of distinct variables

<lambda-formals>     ::= ()
                       | <variable>
                       | (<variable> . <lambda-formals>)

<application>        ::= (<expression> . <expressions>)

where:

• a number is a value that answers #t to the predicate number?;
• a Boolean is a value that answers #t to the predicate boolean?;
• a character is a value that answers #t to the predicate char?;
• a string is a value that answers #t to the predicate string?;
• a symbol is a value that answers #t to the predicate symbol?;
• a variable is a value that answers #t to the predicate symbol? and that is not a keyword (as defined just below); and
• keywords are the symbols define, time, if, cond, else, case, and, or, let, let*, letrec, begin, unless, quote, lambda, and trace-lambda.

Here is some code to get you started. (Note: proper-list-of-given-length? was already defined for arithmetic expressions.)

;;;;;;;;;;

(define check-silently
  #t)

;;;;;;;;;;

(define check-program
  (lambda (v)
    (cond
      [(null? v)
       #t]
      [(pair? v)
       (and (check-toplevel-form (car v))
            (check-program (cdr v)))]
      [else
       (begin
         (unless check-silently
           (printf "check-program -- unrecognized input: ~s~n" v))
         #f)])))

;;;;;;;;;;

(define check-toplevel-form
  (lambda (v)
    (cond
      [(is-definition? v)
       (check-definition (define-1 v) (define-2 v))]
      [else
       (check-expression v)])))

;;;;;;;;;;

;;;;;;;;;;
;;; basic predicates and accessors for definitions:
;;;;;;;;;;

;;; predicate:
(define is-definition?
  (lambda (v)
    (and (proper-list-of-given-length? v 3)
         (equal? (car v) 'define))))

;;; 1st accessor:
(define define-1
  (lambda (v)
    (list-ref v 1)))

;;; 2nd accessor:
(define define-2
  (lambda (v)
    (list-ref v 2)))

;;;;;;;;;;
;;; the syntax checker proper for definitions:
;;;;;;;;;;

(define check-definition
  (lambda (name definiens)
    (and (check-variable name)
         (check-expression definiens))))

;;;;;;;;;;

;;;;;;;;;;
;;; basic predicates and accessors for expressions:
;;;;;;;;;;

;;;;;

;;; predicate:
(define is-number?
  (lambda (v)
    (number? v)))

;;;;;

;;; predicate:
(define is-boolean?
  (lambda (v)
    (boolean? v)))

;;;;;

;;; predicate:
(define is-character?
  (lambda (v)
    (errorf 'is-character? "not implemented yet")))

;;;;;

;;; predicate:
(define is-string?
  (lambda (v)
    (errorf 'is-string? "not implemented yet")))

;;;;;

;;; predicate:
(define is-variable?
  (lambda (v)
    (errorf 'is-variable? "not implemented yet")))

;;;;;

;;; predicate:
(define is-time?
  (lambda (v)
    (and (proper-list-of-given-length? v 2)
         (equal? (car v) 'time))))

;;; 1st accessor:
(define time-1
  (lambda (v)
    (list-ref v 1)))

;;;;;

;;; predicate:
(define is-if?
  (lambda (v)
    (and (proper-list-of-given-length? v 4)
         (equal? (car v) 'if))))

;;; 1st accessor:
(define if-1
  (lambda (v)
    (list-ref v 1)))

;;; 2nd accessor:
(define if-2
  (lambda (v)
    (list-ref v 2)))

;;; 3rd accessor:
(define if-3
  (lambda (v)
    (list-ref v 3)))

;;;;;

;;; predicate:
(define is-unless?
  (lambda (v)
    (and (proper-list-of-given-length? v 3)
         (equal? (car v) 'unless))))

;;; 1st accessor:
(define unless-1
  (lambda (v)
    (list-ref v 1)))

;;; 2nd accessor:
(define unless-2
  (lambda (v)
    (list-ref v 2)))

;;;;;

;;; predicate:
(define is-quote?
  (lambda (v)
    (and (proper-list-of-given-length? v 2)
         (equal? (car v) 'quote))))

;;; 1st accessor:
(define quote-1
  (lambda (v)
    (list-ref v 1)))

;;;;;

;;; predicate:
(define is-application?
  (lambda (v)
    (and (pair? v)
         (let ([w (car v)])
           (if (symbol? w)
               (not (keyword? w))
               #t)))))

;;; 1st accessor:
(define application-operator
  car)

;;; 2nd accessor:
(define application-operands
  cdr)

;;;;;;;;;;
;;; the syntax checker proper for expressions:
;;;;;;;;;;

(define check-expression
  (lambda (v)
    (cond
      [(is-number? v)
       (check-number v)]
      [(is-boolean? v)
       (check-boolean v)]
      [(is-character? v)
       (check-character v)]
      [(is-string? v)
       (check-string v)]
      [(is-variable? v)
       (check-variable v)]
      [(is-time? v)
       (check-time-expression (time-1 v))]
      [(is-if? v)
       (check-if-expression (if-1 v) (if-2 v) (if-3 v))]
      ;;; and
      ;;; or
      ;;; cond
      ;;; etc.
      [(is-unless? v)
       (check-unless-expression (unless-1 v) (unless-2 v))]
      [(is-quote? v)
       (check-quote-expression (quote-1 v))]
      [(is-lambda? v)
       (errorf 'check-expression "not implemented yet")]
      [(is-trace-lambda? v)
       (errorf 'check-expression "not implemented yet")]
      [(is-application? v)
       (check-application (application-operator v) (application-operands v))]
      [else
       (begin
         (unless check-silently
           (printf "check-expression -- unrecognized input: ~s~n" v))
         #f)])))

(define check-number
  (lambda (n)
    #t))

(define check-boolean
  (lambda (b)
    #t))

(define check-character
  (lambda (c)
    (errorf 'check-character "not implemented yet")))

(define check-string
  (lambda (s)
    (errorf 'check-string "not implemented yet")))

(define check-variable
  (lambda (v)
    (errorf 'check-variable "not implemented yet")))

(define check-time-expression
  (lambda (v)
    (check-expression v)))

(define check-if-expression
  (lambda (test consequent alternative)
    (and (check-expression test)
         (check-expression consequent)
         (check-expression alternative))))

(define check-unless-expression
  (lambda (test consequent)
    (and (check-expression test)
         (check-expression consequent))))

(define check-quote-expression
  (lambda (v)
    (errorf 'check-quote-expression "not implemented yet")))

(define check-application
  (lambda (v vs)
    (errorf 'check-application "not implemented yet")))

;;;;;;;;;;
;;; auxiliaries:
;;;;;;;;;;

(define keyword?
  (lambda (w)
    (errorf 'keyword "not implemented yet")))

(define list-strictly-longer-than?
  (lambda (v n)
    (letrec ([visit (lambda (v i)
                      (and (pair? v)
                           (or (= i 0)
                               (visit (cdr v)
                                      (- i 1)))))])
      (if (>= n 0)
          (visit v n)
          (errorf 'list-strictly-longer-than? "negative length: ~s" n)))))

;;; reads an entire file as a list of Scheme data
;;; use: (read-file "filename.scm")
(define read-file
  (lambda (filename)
    (call-with-input-file filename
      (lambda (p)
        (letrec ([visit (lambda ()
                          (let ([in (read p)])
                            (if (eof-object? in)
                                '()
                                (cons in (visit)))))])
          (visit))))))

;;; interface:
(define check-file
  (lambda (filename)
    (if (string? filename)
        (check-program (read-file filename))
        (errorf 'check-file "not a string: ~s" filename))))

;;;;;;;;;;

Example of use:

Chez Scheme Version 8.4
Copyright (c) 1985-2011 Cadence Research Systems

> (load "my-very-own-self-applicable-syntax-checker-oh-yeah.scm")
> (check-file "my-very-own-self-applicable-syntax-checker-oh-yeah.scm")
#t
> (check-expression '(if 1 2 3))
#t
> (check-expression '(time is money))
#f
>

Voilà. Happy hacking.

Resources

• The Scheme code to get you started with your syntax checker (latest version: 12 Oct 2025).

Version

Created [12 Oct 2025]