Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://pavpanchekha.com/blog/adtscm.html below:

Algebraic Data Types in Scheme

Thus, ADT values look like (type-name tag-name field-1-value field-2-value ...). For every ADT, we need to test whether a value is of a given branch, to bind the fields by applying them to a function, and to create a new value from a given branch. In the code, this is accomplished by the function %adt-branch, the % being a convention I picked up from “Let over Lambda”²² “Let over Lambda”, by Doug Hoyte, is a book on macro programming in Common Lisp. It’s available online, the first few chapters being free.

(define (%adt-branch adt-name variant-name num-elts)
  (lambda (op . args)
    (apply ; This apply lets us use Scheme’s parameter list length checking
     (case op
       ((!)
        (lambda elts
          (cons adt-name (cons variant-name elts))))
       ((?)
        (lambda (val)
          (and
           (list? val)
           (= (length val) (+ 2 num-elts)) ; 2 for the ADT and variant name
           (eq? (car val) adt-name)
           (eq? (cadr val) variant-name))))
       ((@)
        (lambda (val f)
          (apply f (cddr val)))))
     args)))

Here, I’m representing an ADT branch by a multiplexed function: a function which takes an operation name and arguments, and executes that operation. Also note the cute trick with apply; this lets multiplexed functions benefit from reasonable parameter number checking and error handling.

With the above structure, we want a match expression, written like

(match val
  ((branch1 field1 field2)
   ...)
  ((branch2 field1)
   ...))

to expand into

(cond
 ((branch1 '? val)
  (branch1 '@ val (lambda (field1 field2) ...)))
 ((branch2 '? val)
  (branch2 '@ val (lambda (field1) ...))))

This can be accomplished by a simple macro:

(define-syntax match
  (syntax-rules (else)
    ((match var ((name vars ...) body ...) rest ...)
     (begin
       (if (name '? var)
           (name '@ var (lambda (vars ...) body ...))
           (match var rest ...))))
    ((match var (else body ...))
     (begin body ...))
    ((match var)
     (error "Incomplete pattern; no match for case" var))))

Finally, we need a way to define an ADT. Really, we need to know only the name of each variant and the number of fields that variant supports. Existing languages with ADTs also need the type of each field; in Scheme we don’t need this, but talking only about the number of fields would lose the self-documentation properties of types. Instead, we’ll require that names for each field be specified, and the number of fields is then just the number of names. An ADT definition then looks like:

(define-adt my-list?
  (my-cons head tail)
  (my-nil))

and a macro that makes this work would be

(define-syntax define-adt
  (syntax-rules ()
    ((define-adt adt-name (name1 fields1 ...) rest ...)
     (begin
       ; This (length '(fields1 ...)) trick is very useful, though
       ; doing it at compile-time would be better.
       (define name1 (%adt-branch 'adt-name 'name1 (length '(fields1 ...))))
       (define-adt adt-name rest ...)))
    ((adt adt-name)
     (define adt-name (%adt-predicate 'adt-name)))))

Note that since Scheme is untyped, it’s pretty important that each logical type be accompanied by a predicate. This predicate is generated by the %adt-predicate function, which hinges on tagging ADT values not just by the branch they represent but also the type they are an instance of.

(define ((%adt-predicate adt-name) val)
  (and (list? val)
       (> (length val) 1)
       (eq? (car val) adt-name)))

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4