search

coalton-lang / coalton

Coalton is an efficient, statically typed functional programming language that supercharges Common Lisp.
https://coalton-lang.github.io/
MIT License
1.16k stars 70 forks source link

TRANSLATE-EXPRESSION on NODE-FOR is buggy #1197

Closed stylewarning closed 3 months ago

stylewarning commented 3 months ago

EDIT:

I thought this was a bug in the inliner, but it appears that the translate-expression method of node-for is doing manual type constructions, and those type constructions are incorrect.

Original post:

repro:

Enable inlining, and

(coalton-codegen
  (define (f)
    (for x in (iter:up-to 5)
      Unit)))

results in

Failed to unify types ITERATOR and OPTIONAL
   [Condition of type COALTON-IMPL/TYPECHECKER/TYPE-ERRORS:UNIFICATION-ERROR]

Restarts:
 0: [RETRY] Retry SLIME REPL evaluation request.
 1: [*ABORT] Return to SLIME's top level.
 2: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING {1001378003}>)

Backtrace:
  0: ((:METHOD COALTON-IMPL/TYPECHECKER/UNIFY::MGU (COALTON-IMPL/TYPECHECKER/TYPES:TYCON COALTON-IMPL/TYPECHECKER/TYPES:TYCON)) ITERATOR OPTIONAL) [fast-method]
      Locals:
        COALTON-IMPL/TYPECHECKER/UNIFY::TYPE1 = ITERATOR
        COALTON-IMPL/TYPECHECKER/UNIFY::TYPE2 = OPTIONAL
  1: ((:METHOD COALTON-IMPL/TYPECHECKER/UNIFY::MGU (COALTON-IMPL/TYPECHECKER/TYPES:TAPP COALTON-IMPL/TYPECHECKER/TYPES:TAPP)) (ITERATOR INTEGER) (OPTIONAL INTEGER)) [fast-method]
      Locals:
        COALTON-IMPL/TYPECHECKER/UNIFY::TYPE1 = (ITERATOR INTEGER)
        COALTON-IMPL/TYPECHECKER/UNIFY::TYPE2 = (OPTIONAL INTEGER)
  2: (COALTON-IMPL/TYPECHECKER/UNIFY:UNIFY COMMON-LISP:NIL (ITERATOR INTEGER) (OPTIONAL INTEGER))
  3: ((:METHOD COALTON-IMPL/CODEGEN/TYPECHECK-NODE:TYPECHECK-NODE (COALTON-IMPL/CODEGEN/AST:NODE-LET COMMON-LISP:T)) #S(COALTON-IMPL/CODEGEN/AST:NODE-LET :TYPE (OPTIONAL INTEGER) :BINDINGS ((X-4450051283 ...
      Locals:
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::ENV = #<COALTON-IMPL/TYPECHECKER/ENVIRONMENT:ENVIRONMENT {101EE9A133}>
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::EXPR = #S(COALTON-IMPL/CODEGEN/AST:NODE-LET ..)
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::SUBEXPR-TY = (ITERATOR INTEGER)
  4: ((:METHOD COALTON-IMPL/CODEGEN/TYPECHECK-NODE:TYPECHECK-NODE (COALTON-IMPL/CODEGEN/AST:NODE-BIND COMMON-LISP:T)) #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND :TYPE #1=UNIT :NAME #:ITER-3585 :EXPR #S(COALTON-..
      Locals:
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::ENV = #<COALTON-IMPL/TYPECHECKER/ENVIRONMENT:ENVIRONMENT {101EE9A133}>
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::EXPR = #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND ..)
  5: ((:METHOD COALTON-IMPL/CODEGEN/TYPECHECK-NODE:TYPECHECK-NODE (COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION COMMON-LISP:T)) #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION :TYPE (#T119838 → UNIT) :VARS (|_51..
      Locals:
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::ENV = #<COALTON-IMPL/TYPECHECKER/ENVIRONMENT:ENVIRONMENT {101EE9A133}>
        COALTON-IMPL/CODEGEN/TYPECHECK-NODE::EXPR = #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION ..)
        COMMON-LISP:TYPE = UNIT
  6: (COALTON-IMPL/CODEGEN/OPTIMIZER:OPTIMIZE-BINDINGS ((F . #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION :TYPE (#T119838 → UNIT) :VARS # :SUBEXPR #))) #<COMMON-LISP:HASH-TABLE :TEST COMMON-LISP:EQ :COUNT ..
      Locals:
        BINDINGS = ((F . #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION :TYPE (#T119838 → UNIT) :VARS (|_51279|) :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND :TYPE UNIT :NAME #:ITER-3585 :EXPR # :BODY #))))
        BINDINGS#1 = ((F . #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION :TYPE (#T119838 → UNIT) :VARS (|_51279|) :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND :TYPE UNIT :NAME #:ITER-3585 :EXPR # :BODY #))))
        ENV = #<COALTON-IMPL/TYPECHECKER/ENVIRONMENT:ENVIRONMENT {101EE9A133}>
        MONOMORPHIZE-TABLE = #<COMMON-LISP:HASH-TABLE :TEST COMMON-LISP:EQ :COUNT 0 {101EE82C73}>
        NAME#1 = F
        NODE#1 = #S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION ..)
        PACKAGE = #<COMMON-LISP:PACKAGE "COALTON-USER">
  7: (COALTON-IMPL/CODEGEN/PROGRAM:COMPILE-TRANSLATION-UNIT #S(COALTON-IMPL/TYPECHECKER/TRANSLATION-UNIT:TRANSLATION-UNIT :TYPES COMMON-LISP:NIL :DEFINITIONS (#S(COALTON-IMPL/TYPECHECKER/TOPLEVEL:TOPLEVEL-..
      Locals:
        ENV = #<COALTON-IMPL/TYPECHECKER/ENVIRONMENT:ENVIRONMENT {101EE82853}>
        MONOMORPHIZE-TABLE = #<COMMON-LISP:HASH-TABLE :TEST COMMON-LISP:EQ :COUNT 0 {101EE82C73}>
        TRANSLATION-UNIT = #S(COALTON-IMPL/TYPECHECKER/TRANSLATION-UNIT:TRANSLATION-UNIT ..)
  8: (COALTON-IMPL/ENTRY:ENTRY-POINT #S(COALTON-IMPL/PARSER/TOPLEVEL:PROGRAM :PACKAGE COMMON-LISP:NIL :FILE #S(SOURCE-ERROR/ERROR:FILE :STREAM #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> :NAME "COALTON-TOPLE..
      Locals:
        PROGRAM = #S(COALTON-IMPL/PARSER/TOPLEVEL:PROGRAM ..)
  9: ((COMMON-LISP:LAMBDA COMMON-LISP:NIL :IN COALTON-IMPL/READER::READ-COALTON-TOPLEVEL-OPEN-PAREN))
      Locals:
        #:G12 = COMMON-LISP:NIL
        COMMON-LISP:STREAM = #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}>
 10: ((:METHOD ECLECTOR.READER:CALL-WITH-LABEL-TRACKING (COMMON-LISP:T COMMON-LISP:T)) #<unused argument> #<FUNCTION (COMMON-LISP:LAMBDA COMMON-LISP:NIL :IN COALTON-IMPL/READER::READ-COALTON-TOPLEVEL-OPEN-..
      Locals:
        ECLECTOR.READER::THUNK = #<FUNCTION (COMMON-LISP:LAMBDA () :IN COALTON-IMPL/READER::READ-COALTON-TOPLEVEL-OPEN-PAREN) {101E6FF0FB}>
 11: ((:METHOD ECLECTOR.READER:CALL-AS-TOP-LEVEL-READ (COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T)) #<COALTON-IMPL/PARSER/READER::COALTON-ECLECTOR-CLIENT {100435950..
 12: ((:METHOD ECLECTOR.READER:CALL-AS-TOP-LEVEL-READ :AROUND (ECLECTOR.PARSE-RESULT:PARSE-RESULT-CLIENT COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T COMMON-LISP:T)) #<COALTON-IMPL/PARSER/READER..
 13: (COALTON-IMPL/READER::READ-COALTON-TOPLEVEL-OPEN-PAREN #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> #\()
 14: (SB-IMPL::READ-MAYBE-NOTHING #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> #\()
 15: (SB-IMPL::%READ-PRESERVING-WHITESPACE #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> COMMON-LISP:T (COMMON-LISP:NIL) COMMON-LISP:T)
 16: (SB-IMPL::%READ-PRESERVING-WHITESPACE #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> COMMON-LISP:T (COMMON-LISP:NIL) COMMON-LISP:NIL)
 17: (COMMON-LISP:READ #<SB-IMPL::STRING-INPUT-STREAM {D68EE93}> COMMON-LISP:T COMMON-LISP:NIL COMMON-LISP:NIL)
 18: (COALTON-IMPL/READER::COMPILE-FORMS COALTON-CODEGEN ((DEFINE (F) (FOR X IN # UNIT))))
 19: (COMMON-LISP:MACROEXPAND-1 (COALTON-CODEGEN (DEFINE (F) (FOR X IN # UNIT))) #<NULL-LEXENV>)
 --more--
stylewarning commented 3 months ago

CC @amorphedstar

The choice of iterator doesn't seem to matter much.

stylewarning commented 3 months ago

Simpler repro:

(coalton-codegen
  (define (f)
    (for x in iter:empty
      Unit)))
stylewarning commented 3 months ago

Last example, node before running inliner:

#S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION
   :TYPE (#T121085 → UNIT)
   :VARS (|_51387|)
   :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND
               :TYPE UNIT
               :NAME #:ITER-3607
               :EXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-APPLICATION
                        :TYPE (OPTIONAL #T121090)
                        :RATOR #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                  :TYPE ((ITERATOR #T121090) → (OPTIONAL #T121090))
                                  :VALUE ITER::|INSTANCE/INTOITERATOR (ITERATOR :A) :A-COALTON-LIBRARY/ITERATOR:INTO-ITER|)
                        :RANDS (#S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                   :TYPE (ITERATOR #T121090)
                                   :VALUE ITER:EMPTY)))
               :BODY #S(COALTON-IMPL/CODEGEN/AST:NODE-WHILE-LET
                        :TYPE UNIT
                        :LABEL :COALTON-LOOP
                        :PATTERN #S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-CONSTRUCTOR
                                    :TYPE (OPTIONAL #T121090)
                                    :NAME SOME
                                    :PATTERNS (#S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-VAR
                                                  :TYPE #T121090
                                                  :NAME X-51386)))
                        :EXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-APPLICATION
                                 :TYPE (OPTIONAL #T121090)
                                 :RATOR #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                           :TYPE ((ITERATOR (ITERATOR #T121090)) → (OPTIONAL #T121090))
                                           :VALUE ITER:NEXT!)
                                 :RANDS (#S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                            :TYPE (ITERATOR (ITERATOR #T121090))
                                            :VALUE #:ITER-3607)))
                        :BODY #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                 :TYPE UNIT
                                 :VALUE UNIT))))

after, fails type checking:

#S(COALTON-IMPL/CODEGEN/AST:NODE-ABSTRACTION
   :TYPE (#T121085 → UNIT)
   :VARS (|_51387|)
   :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-BIND
               :TYPE UNIT
               :NAME #:ITER-3607
               :EXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-LET
                        :TYPE (OPTIONAL #T121090)
                        :BINDINGS ((X-4450051388
                                    . #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                         :TYPE (ITERATOR #T121090)
                                         :VALUE ITER:EMPTY)))
                        :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-LET
                                    :TYPE (ITERATOR #T121137)
                                    :BINDINGS ((X-3966751389
                                                . #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                     :TYPE (ITERATOR #T121136)
                                                     :VALUE X-4450051388)))
                                    :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                :TYPE (ITERATOR #T121138)
                                                :VALUE X-3966751389)))
               :BODY #S(COALTON-IMPL/CODEGEN/AST:NODE-WHILE-LET
                        :TYPE UNIT
                        :LABEL :COALTON-LOOP
                        :PATTERN #S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-CONSTRUCTOR
                                    :TYPE (OPTIONAL #T121090)
                                    :NAME SOME
                                    :PATTERNS (#S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-VAR
                                                  :TYPE #T121090
                                                  :NAME X-51386)))
                        :EXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-LET
                                 :TYPE (OPTIONAL #T121090)
                                 :BINDINGS ((ITER-4414851390
                                             . #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                  :TYPE (ITERATOR (ITERATOR #T121090))
                                                  :VALUE #:ITER-3607)))
                                 :SUBEXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-MATCH
                                             :TYPE (OPTIONAL #T121140)
                                             :EXPR #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                      :TYPE (ITERATOR (ITERATOR #T121139))
                                                      :VALUE ITER-4414851390)
                                             :BRANCHES (#S(COALTON-IMPL/CODEGEN/AST:MATCH-BRANCH
                                                           :PATTERN #S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-CONSTRUCTOR
                                                                       :TYPE (ITERATOR #T121140)
                                                                       :NAME ITER::%ITERATOR
                                                                       :PATTERNS (#S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-VAR
                                                                                     :TYPE (UNIT → (OPTIONAL #T121140))
                                                                                     :NAME ITER::FUNC-44149)
                                                                                  #S(COALTON-IMPL/CODEGEN/PATTERN:PATTERN-WILDCARD
                                                                                     :TYPE (OPTIONAL UFIX))))
                                                           :BODY #S(COALTON-IMPL/CODEGEN/AST:NODE-APPLICATION
                                                                    :TYPE (OPTIONAL #T121140)
                                                                    :RATOR #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                                              :TYPE (UNIT → (OPTIONAL #T121140))
                                                                              :VALUE ITER::FUNC-44149)
                                                                    :RANDS (#S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                                                               :TYPE UNIT
                                                                               :VALUE UNIT)))))))
                        :BODY #S(COALTON-IMPL/CODEGEN/AST:NODE-VARIABLE
                                 :TYPE UNIT
                                 :VALUE UNIT)))
stylewarning commented 3 months ago

I think the inliner is a red herring. Something is wrong with the while-let translation. I think it's buggy.