1. 31
  1.  

  2. 3

    I wish the article were a bit more substantive.

    They touch on type inference. Does anyone have some refs for how to do this in Lisp?

    1. 6

      They touch on type inference. Does anyone have some refs for how to do this in Lisp?

      Henry Baker has a paper about it: The Nimble Type Inferencer for Common Lisp-84

      http://home.pipeline.com/~hbaker1/TInference.html

      1. 4

        You don’t do this, the compiler does it for you. Inferring it from the code, with or without the aid of type declarations by programmer.

        The article has the example of declaring the types, which allows compiler to infer tight, specialized code.

        1. 2

          Sure, agreed. But in my case, I’m implementing the compiler. So I was hoping for some refs on how to do type inference.

          1. 12

            SBCL implements it as type propagation using dataflow analysis. Types in some places are known from explicit declarations, constant literals, known functions, etc., and this information is propagated in a pass named “constraint propagation”, to infer the types of other expressions when possible.

            I’m not sure whether there’s proper documentation anywhere, but this post on some of the type propagator’s weaknesses starts with a summary of how it works [1].

            “Gradual typing” has become a trend outside the Lisp world lately, and I believe those systems do something vaguely similar to propagate types. That might be another place to find implementation hints.

            [1] Note when reading this post that “Python” is the name of SBCL’s compiler; the name predates Guido van Rossum’s language. The reason the compiler has a separate name in the first place is that SBCL’s predecessor, CMUCL, had an interpreter, a bytecode compiler, and a native-code compiler, and Python was the name of the native-code compiler.

            1. 2

              SBCL implements it as type propagation using dataflow analysis. Types in some places are known from explicit declarations, constant literals, known functions, etc., and this information is propagated in a pass named “constraint propagation”, to infer the types of other expressions when possible.

              Ah! Interesting! This is what I was planning to do with my toy lisp :) It might be worth for scholary searches, I heard it first when using Erlang under the name of Succession Typing. I could be completely remembering, but I think Dialyzer uses this method of program typing.

              1. 2

                I don’t think this is quite the same thing as Dialyzer’s Success Typing, though there might be some overlap. Dialyzer’s goals are very different in that it’s only concerned with correctness and not performance. But it might use some similar methods.

            2. 2

              This may help, it’s an overview of FB’s Flow system for JS https://www.youtube.com/watch?v=VEaDsKyDxkY