[racket] An easy route to define-datatype in BSL?

[Prabhakar Ragde]

I'm debating trying to use something like define-datatype, as used in
EOPL and PLAI (and available in the Racket languages that support those
books) early in my first-year undergraduate class. (Opinions on the
wisdom of this, or on my sanity in general, by direct e-mail, please.)

In a teaching-language program, just using `require' to include
define-datatype and type-case or 'cases' from plai/datatype.rkt or
eopl/datatype.rkt appears to work so long as the teaching language is
ISL or higher. In BSL or BSL+, I seem to be running into a thicket of
rules designed to protect students. I'm using as my exploratory example
the trivial arithmetic expression evaluator from the beginning of PLAI
(2007 edition). Using plai/datatype.rkt generates an error because a use
of define-datatype involves function names in expression positions (as
contracts for field names). If I wrap these in applications of
first-order->higher-order from lang/prim, which seems to be designed for
this task, I get an error the first time I try to use a variant
constructor (in the PLAI example, in 'parse'). The constructors seem to
be defined, but also seem to be regarded as variables instead of
functions. This is also what happens with eopl/datatype.rkt (the other
error does not seem to arise).

Do I have a hope of pulling this off, and if so, how? Many thanks. --PR
____________________
Racket Users list:
http://lists.racket-lang.org/users

[Matthew Flatt]

Here's a first cut at a module that you can import into BSL programs.

The least obvious part is defining a new `define-type' and `type-case'
that invents hidden names for the variants and them maps between them
while expanding to the original forms.

----------------------------------------
#lang racket/base
(require plai/datatype
lang/prim
(prefix-in beginner: lang/htdp-beginner)
(for-syntax racket/base
syntax/boundmap))
(provide (rename-out
[my-define-type define-type]
[my-type-case type-case]))

(define-for-syntax variants (make-free-identifier-mapping))
(define-for-syntax (record-variants! vars x-vars)
(for ([var (in-list vars)]
[x-var (in-list x-vars)])
(free-identifier-mapping-put! variants var x-var)))

(define-syntax (my-define-type stx)
(syntax-case stx ()
[(_ ty [var (fld ctc) ...] ...)
(with-syntax ([(x-var ...)
(map (lambda (s)
(datum->syntax
s
(string->uninterned-symbol
(symbol->string (syntax-e s)))
s
s))
(syntax->list #'(var ...)))])
(define (adjust new-stx)
;; `define-type' seems to use the context of the
;; form for `ty?', so copy over old context
(datum->syntax stx (syntax-e new-stx) stx stx))
#`(begin
#,(adjust
#'(define-type ty
[x-var (fld (first-order->higher-order ctc)) ...]
...))
(beginner:define (var fld ...)
(x-var fld ...))
...
(begin-for-syntax
(record-variants! (list #'var ...) (list #'x-var ...)))))]))

(define-syntax (my-type-case stx)
(syntax-case stx ()
[(_ Ty e [var (id ...) rhs] ...)
(with-syntax ([(x-var ...)
(map (lambda (var)
(or (free-identifier-mapping-get
variants
var
(lambda ()
(raise-syntax-error
#f
"not a variant name"
stx
var)))))
(syntax->list #'(var ...)))])
#`(type-case Ty e [x-var (id ...) rhs] ...))]))

[Prabhakar Ragde]

On 2012-11-05 6:43 AM, Matthew Flatt wrote:

> Here's a first cut at a module that you can import into BSL programs.
>
> The least obvious part is defining a new `define-type' and `type-case'
> that invents hidden names for the variants and them maps between them
> while expanding to the original forms.

Wow, thanks. I will study the code and do my best to understand it, and
test it for deployment next fall. I can already see the outline of how
your code achieves what you describe, but could you please say a few
words about why that's necessary, to improve my understanding of BSL?
Thanks again. --PR

[Matthew Flatt]

At Mon, 05 Nov 2012 08:13:16 -0500, Prabhakar Ragde wrote:
> On 2012-11-05 6:43 AM, Matthew Flatt wrote:
>
> > Here's a first cut at a module that you can import into BSL programs.
> >
> > The least obvious part is defining a new `define-type' and `type-case'
> > that invents hidden names for the variants and them maps between them
> > while expanding to the original forms.
>
> Wow, thanks. I will study the code and do my best to understand it, and
> test it for deployment next fall. I can already see the outline of how
> your code achieves what you describe, but could you please say a few
> words about why that's necessary, to improve my understanding of BSL?
> Thanks again. --PR

You had worked out the need for `first-order->higher-order' on
contracts for variant fields. The flip side is using BSL's `define' to
define variant constructors so that BSL is willing to see them used in
an application position.

But if the constructors are defined with BSL's `define', then you have
to give different names to the variants as defined by `define-type', so
those can be wrapped by BSL-friendly definitions. The last piece, then,
is to rewrite variant names in a `type-case' (which correspond to the
BSL-`define'd wrappers) to the names as defined by `define-type'.

[Jay McCarthy]

BSL uses special syntax information (installed by beginner:define) to only allow applications on first-order functions. For example,

(define (f a)

 (a 1))

is an error in BSL. The way this is detected is that every top-level define (like for 'f') has a special notation on it that says "I'm a function". Since 'a' doesn't have this, then the macro for app in BSL can throw an error.

The main thing that this macro does is give that information to the identifiers, but you need to redefine them, which causes the need for the variant mapping since type-case is looking for the original variant names.

Jay

--
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93

[Grant Rettke]

On Mon, Nov 5, 2012 at 7:22 AM, Jay McCarthy <jay.mc...@gmail.com> wrote:

every top-level define (like for 'f') has a special notation on it that says "I'm a function". Since 'a' doesn't have this, then the macro for app in BSL can throw an error.

What Racket language feature is used to do that? 

[Jay McCarthy]

I think they are macro bindings that are actually structures with prop:procedure functions, so that the app macro (like 'special') below, can check where they came from.

#lang racket

(struct example (f x)

        #:property

        prop:procedure

        (λ (e y)

          ((example-f e) (example-x e) y)))

(define a (example + 4))

(a 5)

(begin-for-syntax

  (require racket/list)

  (struct macro-example (f x)

          #:property

          prop:procedure

          (λ (e y)

            ((macro-example-f e) 

             (macro-example-x e)

             y))))

(define-syntax macro-a 

  (macro-example 

   (λ (now then)

     #`(+ #,now #,@(rest (syntax->list then))))

   #'4))

(macro-a 5)

(define-syntax (special stx)

  (syntax-case stx ()

    [(_ f e)

     (macro-example? (syntax-local-value #'f (λ () #f)))

     #'(f e)]

    [_

     #'42]))

(special macro-a 5)

(special a 5)