[racket] typed racket cps, state machines

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: OpenPGP digital signature
URL: <http://lists.racket-lang.org/users/archive/attachments/20140905/c38dac4c/attachment.sig>