[racket] typed racket cps, state machines

Would this do for you: 

#lang typed/racket

(require typed/rackunit)

(define-type Answer Boolean)

(: find (All (α) (-> (-> α Boolean) (Listof α) (-> (Listof α) Answer) (-> Answer) Answer)))
(define (find pred? l sk fk)
  (cond
    [(empty? l) (fk)]
    [(pred? (first l)) (sk l)]
    [else (find pred? (rest l) sk fk)]))
                       
(check-equal? (find odd? '(2 3 4) (λ (x) #t) (λ () #f)) #t)





On Sep 5, 2014, at 3:48 PM, Anthony Carrico wrote:

> On 09/05/2014 11:48 AM, Matthias Felleisen wrote:>
>> 1. Your programs don't look like conventional cps...
> 
> I have distilled my "cps-ish" examples too far away from any context. A
> concrete example of this pattern would be searching. The direct style is:
> 
> (findf proc lst) -> any/c
> 
> When I say "cps-ish", I'm talking about the following style:
> 
> (find proc lst found-tail not-found-tail)
> 
> the type turns out to be something like this:
> 
> (: find (Any (Element FoundV NotFoundV)
>   (-> (-> Element Boolean) (Listof Element)
>       (-> Element FoundV)
>       (-> NotFoundV)
>       (U FoundV NotFoundV)))
> 
> In my mind, the computation is essentially "returning" to either the
> found-tail, or the not-found-tail. The result types of the tails are
> irrelevant to the search computation; they don't show up in direct style
> version. Another way to express this would be with two return points, in
> the multi-return lambda calculus of Shivers/Fisher, where findf could be:
> 
> (: findf (Any (Element) (-> Element Boolean) (Listof Element) <Element,
> Void>))
> 
> Here are there are two return points, <Element, Void>, found and not found.
> 
> This pattern does show up occasionally in plain old racket code.
> Sometimes the pattern translates easily to TR, but sometimes not. In my
> looping "state machine" example, I had a scanner or parser in mind which
> would exit through one of the tails.
> 
>> 2. Don't use polymorphism.
> 
> Apparently. I was trying to figure out if this is something I don't know
> how to annotate properly, or something that really requires a code
> transformation to type.
> 
>> 3. Think about the algorithm. This hint comes in the form of a cps
>> algorithm:
> 
> Thank you for the cps converter. I'm not sure if it is relevant to the
> intended question, but I think I will write the evaluator you suggest as
> an exercise.
> 
> -- 
> Anthony Carrico
> 
>