I've been exploring Racket macros and have a question regarding performance and types.
Is there a way in Racket to achieve zero-overhead type dispatch similar to C++ templates? Specifically, I want the macro to generate different code paths based on the types of the arguments at compile-time, avoiding runtime overhead.
For example, I want to write a macro my-add that behaves like this:
;; Pseudo-code expectation
(define x : Integer 1)
(my-add x x) ;; -> expands to (fx+ x x) for performance
(define y : Float 1.0)
(my-add y y) ;; -> expands to (fl+ y y)
Can this be achieved using typed/racket alone, or do I need to dig deeper into other mechanisms?
I am aware of Turnstile , but I find its heavy reliance on Unicode symbols to be a significant engineering drawback for my workflow. I am looking for a more idiomatic or standard approach.
My understanding is that this isn’t currently something possible in Typed Racket, because Typed Racket typechecks fully-expanded programs, while type-directed dispatch requires more careful control of expansion vs. typechecking. You would need a separate #lang that implements such feature, but then the interop with Racket wouldn’t be as smooth as Typed Racket–Racket.
For some cases, TR can perform such optimizations for you.
Example: Vincent St-Amour pushed an FFT really hard in this
direction so that the standard formulation using Complex
numbers achieved the performance of a hand-rolled optimization.
He implemented an ‘optimization coach’ that provides feedback
to a programmer when an optimization got almost triggered.
In some cases, the programmer can then take corrective action
meaning a code rewrite that triggers the optimization.
As @usao points out, you cannot use macros for this purpose.
TR expands all macros before it checks types.
[[ Note though that anyone who says "zero overhead" in computing
isn't telling you the whole truth. There's no free lunch. ]]
[I’ve heard that typed/racket could pass type information along with syntax objects? Is there a way to force early expansion of macros to extract type information? (I’ve heard of something like local-expand.)]
以及还是同样的问题，如何实现基于类型的特设多态？
[And the same question: how to implement ad-hoc polymorphism based on types?]
Typed Racket 的设计上来说是没有办法在展开宏的时候提供类型信息的，因为类型检查发生在宏展开之后。就算使用了 local-expand 去提前展开子表达式，因为类型检查并没有发生，所以也不能推导它们的类型。这个设计本身是为了令 Typed Racket 和 Racket 之间的互操作可以更平滑。例如说，Racket 的宏，像是用于模式匹配的 match，可以直接在 Typed Racket 里使用（当然，展开后的代码本身要能够被类型检查）。同时，来自 Typed Racket 的函数等高阶值也可以在包装高阶契约后直接在 Racket 里使用。（关于这方面的技术细节，可以看《Advanced Macrology and the Implementation of Typed Scheme》或者《Typed Scheme: From Scripts to Programs》。）
[Due to its design, Typed Racket cannot provide type information when expanding macros, because typechecking happens after macro expansion. Even if you use local-expand to early expand sub-expressions, since typechecking hasn’t happened yet, you cannot infer their types. This design was to made the interop between Typed Racket and Racket smoother. For example, Racket macros, such as match for pattern matching, can be used directly in Typed Racket (provided that the expanded code is typecheckable). At the same time, higher-order values such as functions from Typed Racket, wrapped with higher-order contracts, can be used directly in Racket. (For the relevant technical details, you can refer to “Advanced Macrology and the Implementation of Typed Scheme” or Typed Scheme: From Scripts to Programs.)]
如果要实现类型导向的宏，可以参考《Type Systems as Macros》里的技术，例如 Turnstile 的实现。简单点来说，就是用宏系统去实现一种双向类型推导，所以宏可以控制子表达式的类型推导。这方面的具体例子的话可以参考 Hackett；Hackett 是独立使用了这个技术去实现类型系统。当然，最终还是离不开要实现一个单独的 #lang，和 Racket 的互操作也会没那么平滑。
[To implement type-directed macros, you can refer to the technique in “Type Systems as Macros”, such as implemented by Turnstile. To put it simply, if you use the macro system to implement a kind of bidirectional type inference, macros are able to control the type inference of sub-expressions. For a concrete example, see Hackett, which implements its type system independently using such technique. At the end of the day, you would have to implement a separate #lang, which wouldn’t interop with Racket as smoothly.]
[ Thanks for your reply. I searched through some mailing lists and Q&A threads yesterday, including replies from Felleisen and the creator of Typed Racket . It seems that implementing type-based ad-hoc polymorphism using only Typed Racket is essentially impossible.]
felleisen 的回复中说这是 racket 设计的一个历史权衡，即特设多态不符合 scheme 的设计哲学。
[ In his response, Felleisen mentioned that this is a historical trade-off in Racket's design—specifically, that ad-hoc polymorphism does not align with Scheme's design philosophy.]
我想这是无解的，不过 turnstile 等提供了一些替代方案，费的事就比较多。
[I suppose there is no direct solution to this. While tools like Turnstile provide some alternatives, they require significantly more effort to implement.]
按理说如果 case-lambda 能够按类型分派，也不会这么难受。我不知道这个工程实现的难度如何。
[Ideally, if case-lambda could perform dispatch based on types, it wouldn't be so frustrating. I'm not sure how difficult this would be from an engineering perspective.]
不过现在的 typed/racket 既没有在语言原生功能中提供基于类型的特设多态，也很难让用户自己实现（类型系统和宏系统协作的很差），就非常恼火了。
[However, current Typed Racket neither provides native support for type-based ad-hoc polymorphism nor makes it easy for users to implement it themselves (as the type system and macro system do not collaborate well), which is quite annoying.]
This just ideas. Perhaps some type dispatch could be achieved with syntax transformers "before" running?
Another idea, would be to have a pre-parser before Scheme/Racket compilation that change the syntax ,dispatching the good procedures depending of type.
This could be done using explicit typing or type inference (harder, as Haskell do it)
In Scheme+ i use a pre-parser before Scheme/Racket compilation.If i add type definitions in the source code i would be able to parse the definitions to adapt the code depending of the type annotation inserted in source code. This way the type dispatch will be zero-overhead because not at runtime.
It is an idea i have, unfortunately, i have not time for that now and i can not evaluate the complexity and time such a process can take to implement it.
But this is an interesting idea for the future. Complex also because each Scheme that use some type annotation ,for example Bigloo, or Kawa (?) or typed Racket have it own way to define type annotation.
First it would be usefull to adopt an uniform way for type annotation.