How do I create a "probability" HOF (or syntax) in typed racket

Question

I am trying to create an HOF in typed racket which will allow me to express the idea, "at evaluation time, roll the dice and pick the procedure to apply".

Currently, I am working with the following:

(: odds-on ((Any * -> Any) (Any * -> Any) Real -> (Any * -> Any)))
(define (odds-on choice alternative odds)
  (cond [(< (random) odds) choice]
    [else alternative]))

with the idea being I could use it like this:

> ((odds-on do-a-common-thing do-a-rarer-thing .75) 'x '(a b c) (set z))

where do-a-common-thing and do-a-rarer-thing are defined elsewhere, and may have arbitrary argument arity and types. So that about 3/4 of the time the first function would be called, and 1/4 the second would.

But I'm running into type-checking and arity issues left and right... Based on the docs, I need heterogenous rest arguments, but I don't follow the docs very well, not being a scholar of type systems... I simply want to be able to specify two functions and a probability, and have the function which is called be determined at runtime!

And, overall, maybe a macro/syntax form would be a more sensible way to create this effect? From an interface design standpoint, this capability is exactly what I need in my program, but I don't know how to implement it with static types... But I want the static types to help keep a handle on other parts of the program.

Answer 1

Let me propose a simpler (in some ways) type for your example:

(: odds-on (All (X Y) (X Y Real -> (U X Y))))
(define (odds-on choice alternative odds) 
  (cond [(< (random) odds) choice]
        [else alternative]))

and using it like this:

-> ((odds-on (lambda () (displayln "hi"))
             (lambda () (displayln "bye"))
             0.75))
bye
-> ((odds-on (lambda ([x : String]) (string-append x "1"))
             (lambda ([x : String]) (string-append x "2"))
             0.23)
    "test")
- : String
"test2"

There's a bit of a tradeoff here though, since now you can pass odds-on things that aren't actually functions. If you do happen to pass odds-on some non-function values, you won't be able to call the returned value though (i.e., the type-checker will catch it later anyway).

(Note: as an aside, if Typed Racket supported bounded polymorphism you would be able to express a constraint that X and Y must be functions in this example. That's potentially future work for TR.)

There's also the (U X Y) in the return type that you have to be careful about. If you pass odds-on two functions with incompatible argument arities, it will be more difficult to call the resulting function.

-> ((odds-on (lambda () (displayln "hi"))
             (lambda (x) (displayln "bye"))
             0.75))
; readline-input:10:0: Type Checker: could not apply function;
;  wrong number of arguments provided
;   expected: 1
;   given: 0
;   in: ((odds-on (lambda () (displayln "hi")) (lambda (x) (displayln "bye"))
;     0.75))
; [,bt for context]

(Note: your error message may look different. I'm running Racket v6.0.0.4. Also, this error message is not so great.)

Answer 2

I'm still new to Typed Racket so I don't think this is a great answer.

The type (Any * -> Any) is for a homogenous rest argument. So the function need to actually take a rest argument, e.g. (define (f . xs) ...) or (lambda xs ...). If I change your example accordingly, it type checks for me:

#lang typed/racket

(: odds-on ((Any * -> Any) (Any * -> Any) Real -> (Any * -> Any)))
(define (odds-on choice alternative odds)
  (cond [(< (random) odds) choice]
        [else alternative]))

((odds-on (lambda xs (second xs)) ;; <--
          (lambda xs (third xs))  ;; <--
          0.75)
 'x 'y 'z)

Of course, you may not really want the functions to take a rest argument like xs instead of normal arguments like x y z. You might be using rest arguments only in an attempt to find something that will type check. In that case I don't know what to tell you (yet).

---

UPDATE: In light of your comment, I took another crack at this, using the Procedure type, but it didn't turn out very well.

#lang typed/racket

(: odds-on (Procedure Procedure Real -> Procedure))
(define (odds-on choice alternative odds)
  (cond [(< (random) odds) choice]
        [else alternative]))

(define x (odds-on (lambda () #t)
                   (lambda () #f)
                   0.75))

x
; - : Procedure
; #<procedure:/tmp/tr.rkt:9:10>

(x)
; stdin::12271: Type Checker: Cannot apply expression of type Procedure, since it is not a function type
;   in: (x)

On the one hand, x is a Procedure. On the other hand, x can't be applied because it's not a Procedure. And on the third hand, I am confuse.

UPDATE: The reason this doesn't work is that Procedure is a sort of "opaque" type that means, "This thing satisfies procedure? but we won't know anything more -- and therefore don't know how to call it safely". That is the sense in which the error message's Zen koan, "Procedure is not a function type", actually does make sense.

Asumu's answer is better.