Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

pyret-for - a new way to call higher order functions #11

Open
sorawee opened this issue Aug 3, 2021 · 7 comments
Open

pyret-for - a new way to call higher order functions #11

sorawee opened this issue Aug 3, 2021 · 7 comments

Comments

@sorawee
Copy link

sorawee commented Aug 3, 2021

Many common higher-order functions consume a function value as the first argument, and n more arguments after that, where the function value accepts n arguments, which corresponds to the arguments in the call in some way. Examples include: map, filter (only one argument), andmap, ormap (foldl and foldr have arguments in a wrong order, so they don't quite work)

Example code without pyret-for

(define things     '(("pen") ("pineapple") ("apple") ("pen")))
(define quantities '(1       2             3         5))

(andmap (λ (thing quantity)
          (or (string-contains? (first thing) "apple")
              (odd? quantity)))
        things
        quantities)

The problem is that

  • It's difficult for readers to relate formal arguments of the function value to the actual arguments of the call.
  • There's a lot of rightward drift.

Example code with pyret-for

(define things     '(("pen") ("pineapple") ("apple") ("pen")))
(define quantities '(1       2             3         5))

(pyret-for andmap ([thing things] [quantity quantities])
  (or (string-contains? (first thing) "apple")
      (odd? quantity)))

The pyret-for syntax, based on Pyret's for, can be used to invoke this kind of higher-order functions.

pyret-for additionally improves upon Pyret's for by allowing arbitrary match pattern.

(define things     '(("pen") ("pineapple") ("apple") ("pen")))
(define quantities '(1       2             3         5))

(pyret-for andmap ([(list thing) things] [quantity quantities])
  (or (string-contains? thing "apple")
      (odd? quantity)))

Macro

(require syntax/parse/define)

(define-syntax-parse-rule (pyret-for f:expr ([pat:expr arg:expr] ...) body:expr ...+)
  #:with (x ...) (generate-temporaries (attribute arg)) 
  (f (λ (x ...)
       (match-define pat x) ...
       body ...)
     arg ...))

Licence

MIT License / CC BY 4.0

@bennn
Copy link
Member

bennn commented Aug 5, 2021

Great idea! I really like how small the macro is.

I wonder if we can think of a clearer name. I like that pyret-for gives credit to Pyret and gives a hint about one good way to use this macro (for-style loops). But it doesn't say much about what's really going on ... and if we understood that, maybe we'd find other ways to use this macro.

polydot-apply ?
map-comprehension ?

@sorawee
Copy link
Author

sorawee commented Aug 6, 2021

I'm not sure what "polydot" means.

comprehension could work, I think. I would avoid map-, since it supports more than map.

@bennn
Copy link
Member

bennn commented Aug 10, 2021

Oh, "polydot" is the local name for the polymorphic dotted (...) types that work for typing map fold etc. [1]. Typed Racket uses that name internally [link]. I don't know where else to find it in print.

Anyway, I was thinking that polydot-typed functions have something in common that makes them fit well with pyret-for .

But looking back at your original message, I see that filter also works well with pyret-for. So I guess "polydot" is too specific.

[1] Practical Variable Arity Polymorphism. ESOP 2009

@bennn
Copy link
Member

bennn commented Aug 13, 2021

Today I explained this pyret-for macro to a few people at Brown. While thinking about it, we came up with one way to generalize:

(apply/lambda f (arg-spec ...) body ...)

where arg-spec is one of:
- #:hole
- #:from [id expr]
- expr

and the sequence (arg-spec ....) has exactly one #:hole 

expands to:
(let ((g (lambda (id ...) body ...)))
  (apply f (convert/g arg-spec) ...))

where convert/g:
- replaces #:hole with g
- replaces #:from [id expr] with expr
- and leaves other expr alone

I like #:hole a lot. That'd help this macro work with foldl.

The other (non-#:from) arguments would be inputs to f that don't get passed along to the newly-built lambda.

@sorawee
Copy link
Author

sorawee commented Aug 14, 2021

Like this?

#lang racket

(require syntax/parse/define
         (for-syntax racket/match
                     racket/list))

(begin-for-syntax
  (define-syntax-class arg-spec
    #:attributes ([tmp-id 1] gen-match-code expr)
    (pattern #:proc
             #:with (tmp-id ...) #'()
             #:with gen-match-code #'(begin)
             #:with expr #'the-function)
    (pattern [pat:expr #:from expr:expr]
             #:with (tmp-id ...) (generate-temporaries (list #'id))
             #:with gen-match-code #'(begin (match-define pat tmp-id) ...))
    (pattern expr:expr
             #:with (tmp-id ...) #'()
             #:with gen-match-code #'(begin)))

  (define (validate-proc-once args)
    (define proc-list
      (filter (λ (arg) (equal? '#:proc (syntax-e arg))) (syntax->list args)))
    (match (length proc-list)
      [1 #f]
      [0 args]
      [_ (first proc-list)])))

(define-syntax-parse-rule (apply/λ f:expr {~and args (arg:arg-spec ...+)} body:expr ...+)
  #:fail-when (validate-proc-once #'args) "#:proc must appear exactly once"
  (let ([the-function (λ ({~@ arg.tmp-id ...} ...)
                        arg.gen-match-code ...
                        body ...)])
    (f arg.expr ...)))

(apply/λ andmap (#:proc [(list x) #:from '((1) (2) (3))] [y #:from '(3 2 1)])
  (even? (+ x y)))

(define (hof offset xs proc)
  (+ offset (apply + (map proc xs))))

(apply/λ hof (100 [x #:from '(1 2 3)] #:proc)
  (* 2 x))

foldl and foldr unfortunately still couldn't be expressed with this generalization.

@bennn
Copy link
Member

bennn commented Aug 20, 2021

Ah! I didn't mean to make you implement it --- I thought we were just talking about possibilities.

That's awful about fold. I guess I'd want #:proc to take an (optional?) arg to give the order of parameters, but that screws up the match-define ....

;; ... something like this
(apply/λ foldl (#:proc (x* y acc) [acc #:from 0] [(list x) #:id x* #:from '((1) (2) (3))] [y #:from '(3 2 1)])
  (+ x y acc))

😞

@sorawee
Copy link
Author

sorawee commented Aug 20, 2021

Actually, my version above also has a bug. I should check 'paren-shape for [<x> #:from <y>]. Otherwise, a function application (some-function #:from 123) will be parsed as a apply/λ binding.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants