On Monday, September 5, 2016 at 10:54:57 PM UTC+5:30, Matthias Felleisen wrote:
> The easiest and proper fix is to write typed macros for typed modules. Below
> is a naive but straightforward solution. It would be better if
> define-memoized fished out the type declaration for f and used it to add
> domain types for arg-s...
>
> #lang typed/racket
>
> (require (for-syntax syntax/parse))
>
> (: memoize (All (r a ...)
> (-> (-> a ... a r)
> (-> a ... a r))))
> (define (memoize fn)
> (let ([store : (HashTable Any r) (make-hash)])
> (define (memfn . [args : a ... a])
> (hash-ref store args
> (lambda ()
> (let ([result : r (apply fn args)])
> (hash-set! store args result)
> result))))
> memfn))
>
> (: fibo (-> Integer Integer))
> (define fibo (memoize (lambda ([n : Integer])
> (if (<= n 1)
> 1
> (+ (fibo (- n 1))
> (fibo (- n 2)))))))
>
> (define-syntax (define-memoized stx)
> (syntax-parse stx ;; I didn’t get the ‘:’ syntax right the first time, so I
> gave up on that
> [(_ (fn-name:id {arg t} ...) Tresult body ...)
> #'(begin
> (: fn-name (-> t ... Tresult))
> (define fn-name (memoize (lambda ({arg : t} ...) body ...))))]))
>
>
> (define-memoized (fib {n Integer}) Integer
> (if (<= n 1)
> 1
> (+ (fib (- n 1))
> (fib (- n 2)))))
>
> (fib 10)
>
>
>
> > On Sep 5, 2016, at 3:11 AM, Sourav Datta <[email protected]> wrote:
> >
> > Another day, another typed racket question!
> >
> > I was experimenting with memoize library in Racket and noticed that it does
> > not always work with typed racket functions (or, may be I was not
> > 'require'ing it properly). So I came up with this crude implementation
> > below and it seems to be working for one or more arguments:
> >
> > #lang typed/racket
> >
> > (: memoize (All (r a ...)
> > (-> (-> a ... a r)
> > (-> a ... a r))))
> > (define (memoize fn)
> > (let ([store : (HashTable Any r) (make-hash)])
> > (define (memfn . [args : a ... a])
> > (hash-ref store args
> > (lambda ()
> > (let ([result : r (apply fn args)])
> > (hash-set! store args result)
> > result))))
> > memfn))
> >
> > So the typical fibo function with this memoization function would look like:
> >
> > (: fibo (-> Integer Integer))
> > (define fibo (memoize (lambda ([n : Integer])
> > (if (<= n 1)
> > 1
> > (+ (fibo (- n 1))
> > (fibo (- n 2)))))))
> >
> > However, what I wanted is to define a macro similar to define/memo like in
> > the Racket memoize package. A first approach like below did not work:
> >
> > (define-syntax (define-memoized stx)
> > (syntax-parse stx
> > [(_ (fn-name:id arg:id ...) body ...+)
> > #'(define fn-name (memoize (lambda (arg ...) body ...)))]))
> >
> > The error comes in (<= n 1) call where it is given Any but expecting
> > Integer. The problem is that the syntax splits the function definition in a
> > lambda expression and then passes to memoize function, whose result is then
> > assigned to the function name. The lambda expression without type
> > annotation assumes that the arguments are Any.
> >
> > So in this case, is there any way we could write a macro on top of the
> > above memoize that can identify the types of the underlying function and
> > annotate the lambda accordingly - or is there any other way this could be
> > achieved?
> >
> > Thanks!
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Racket Users" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to [email protected].
> > For more options, visit https://groups.google.com/d/optout.
This approach seems like the easiest and flexible way to define the macro. Just
to add, here's another crude version of the macro I came up with where we can
specify the type declaration inside the macro, rather than outside which gives
some way to use it in the function definition:
(define-syntax (memoized stx)
(syntax-parse stx
((_ type-decl (define (fn-name:id arg:id ...+) body ...+))
(let ([type-decl-v (syntax->datum #'type-decl)])
(if (not (and (list? type-decl-v)
(eqv? (car type-decl-v) ':)))
(error "Bad type declaration!")
(let* ([new-fn-name (gensym)]
[old-fn-name (syntax->datum #'fn-name)]
[new-type-decl-v (map (lambda (s) (if (equal? s old-fn-name)
new-fn-name s)) type-decl-v)])
(with-syntax ([fn-temp-name (datum->syntax stx new-fn-name)]
[new-type-decl (datum->syntax stx new-type-decl-v)])
#'(begin
new-type-decl
(define (fn-temp-name arg ...) body ...)
type-decl
(define fn-name (memoize fn-temp-name))))))))
((_ (define (fn-name:id arg:id ...+) body ...+))
#'(define fn-name (memoize (lambda (arg ...) body ...))))))
And now the fibo definition becomes like this:
(memoized
(: fibo (-> Integer Integer))
(define (fibo n)
(if (<= n 1)
n
(+ (fibo (- n 1))
(fibo (- n 2))))))
Of course this now itroduces a temporary function with the actual definition as
a drawback.
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
