Sixten

Types

data Lowered = Lowered !Lifted !LoweredKind
  deriving (Eq, Ord, Show, Generic)

data Lifted = Lifted !Qualified !Int
  deriving (Eq, Ord, Show, Generic)

Queries

digraph sixty_queries {
  bgcolor="transparent"

  node [
    style=filled
    fillcolor=gray95
  ]

  ModuleFile -> InputFiles
  ModuleFile -> SourceDirectories
  ParsedFile -> FileText
  ParsedFile -> SourceDirectories
  ModuleDefinitions -> ModuleFile
  ModuleDefinitions -> ParsedFile
  ModuleHeader -> ModuleFile
  ModuleHeader -> ParsedFile
  ModuleHeader -> ModuleFile
  ImportedNames -> ImportedNames
  ImportedNames -> ModuleHeader
  ImportedNames -> ModuleHeader
  ImportedNames -> ModuleScope
  NameAliases -> ImportedNames
  NameAliases -> ModuleScope
  ParsedDefinition -> ParsedDefinition
  ParsedDefinition -> ModuleFile
  ParsedDefinition -> ParsedFile
  ModulePositionMap -> ModuleSpanMap
  ModuleSpanMap -> ModuleFile
  ModuleSpanMap -> FileText
  ModuleSpanMap -> ParsedFile
  ModuleScope -> ModuleFile
  ModuleScope -> ParsedFile
  ModuleScope -> "Resolution.moduleScopes"
  "Resolution.moduleScopes" [ shape="record" ]
  ResolvedName -> ModuleScope
  ResolvedName -> ImportedNames
  ElaboratingDefinition -> ParsedDefinition
  ElaboratingDefinition -> ParsedDefinition
  ElaboratingDefinition -> ElaboratedType
  ElaboratingDefinition -> ElaboratedType
  ElaboratedType -> ElaboratingDefinition
  ElaboratedType -> ElaboratedDefinition
  ElaboratedType -> ElaboratedType
  ElaboratedDefinition -> ElaboratingDefinition
  ElaboratedDefinition -> ElaboratedType
  Dependencies -> Dependencies
  Dependencies -> ElaboratedDefinition
  TransitiveDependencies -> TransitiveDependencies
  TransitiveDependencies -> TransitiveDependencies
  TransitiveDependencies -> Dependencies
  TransitiveDependencies -> Dependencies
  ConstructorType -> ElaboratedDefinition
  DefinitionPosition -> ModulePositionMap
  DefinitionPosition -> ModuleFile
  Occurrences -> Occurrences
  Occurrences -> Occurrences
  LambdaLifted -> ElaboratedDefinition
  LambdaLiftedDefinition -> LambdaLifted
  LambdaLiftedDefinition -> LambdaLifted
  LambdaLiftedDefinition -> LambdaLifted
  LambdaLiftedModuleDefinitions -> ModuleDefinitions
  LambdaLiftedModuleDefinitions -> LambdaLifted
  ClosureConverted -> LambdaLiftedDefinition
  ClosureConvertedType -> ClosureConverted
  ClosureConvertedType -> ClosureConverted
  ClosureConvertedType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConvertedConstructorType
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConverted
  ClosureConvertedConstructorType -> ClosureConvertedConstructorType
  ClosureConvertedConstructorType -> ClosureConvertedConstructorType
  LowSignature -> ClosureConverted
  LowSignature -> ClosureConverted
  LoweredDefinitions -> ClosureConverted
  LoweredDefinitions -> "Lower.definition"
  "Lower.definition" [ shape="record" ]
  "Lower.definition" -> LowSignature
  "Lower.definition" -> ConstructorRepresentations
  "Lower.definition" -> ClosureConvertedConstructorType
  ConstructorRepresentations -> ClosureConverted
  ConstructorRepresentation -> ConstructorRepresentations
  LowDefinitions -> ClosureConverted
  LowModule -> LambdaLiftedModuleDefinitions
  LowModule -> LowDefinitions
  ReferenceCountedLowModule -> LowModule
  LLVMModule -> ReferenceCountedLowModule
  LLVMModuleInitModule -> InputFiles
  LLVMModuleInitModule -> ParsedFile

  ElaboratingDefinition -> "Elaboration.checkDefinition"
  "Elaboration.checkDefinition" [ shape="record" ]
  "Elaboration.checkDefinition" -> "Elaboration.check"
  "Elaboration.elaborateWith" [ shape="record" ]
  "Elaboration.elaborateWith" -> "Elaboration.elaborate"
  "Elaboration.elaborateWith" -> ResolvedName
  "Elaboration.elaborateWith" -> ElaboratedType
  "Elaboration.elaborateWith" -> ConstructorType
  "Elaboration.elaborate" [ shape="record" ]
  "Elaboration.infer" [ shape="record" ]
  "Elaboration.infer" -> "Elaboration.elaborate"
  "Elaboration.check" -> "Elaboration.elaborate"
  "Elaboration.elaborate" -> "Elaboration.elaborateWith"
  "Elaboration.check" -> "Elaboration.elaborate"
  "Elaboration.check" [ shape="record" ]
}

file:sixty-query-call-graph.png

  ModuleDefinitions :: Name.Module -> Query (OrderedHashSet Name)

  LambdaLiftedModuleDefinitions :: Name.Module -> Query (OrderedHashSet Name.Lifted)

    LambdaLiftedModuleDefinitions module_ ->
      noError do
        names <- fetch $ ModuleDefinitions module_
        OrderedHashSet.fromList . concat
          <$> forM (toList names) \name -> do
            let qualifiedName =
                 -- Each name from the source module is adorned with the module
                 -- name.
                  Name.Qualified module_ name
            (_, extras) <- fetch $ LambdaLifted qualifiedName
            -- I'm not sure what's going on with the EnumMap here...
            pure $ Name.Lifted qualifiedName <$> 0 : EnumMap.keys extras

  ResolvedName :: Name.Module -> Name.Surface -> Query (Maybe Scope.Entry)

    ResolvedName module_ surfaceName ->
      noError do
        -- Notice the particular use of privateScope!
        (privateScope, _) <- fetch $ ModuleScope module_
        importedScopeEntry <- fetchImportedName module_ surfaceName
        pure $ importedScopeEntry <> HashMap.lookup surfaceName privateScope

  ModuleScope :: Name.Module -> Query (Scope, Scope)

  ImportedNames :: Name.Module -> Mapped.Query Name.Surface Scope.Entry a -> Query a

    ImportedNames module_ subQuery ->
      noError $
        Mapped.rule (ImportedNames module_) subQuery do
          header <- fetch $ ModuleHeader module_
          scopes <- forM header.imports \import_ -> do
            importedHeader <- fetch $ ModuleHeader import_.module_
            (_, publicScope) <- fetch $ ModuleScope import_.module_
            pure $
              Resolution.importedNames import_ $
                Resolution.exposedNames importedHeader.exposedNames publicScope

          pure $ foldl' (HashMap.unionWith (<>)) mempty scopes

Driver

See: src/Compiler.hs Some key takeaways:

• The set of source files is fetched with a query.

• Source files appear to be processed in arbitrary order, with no regard to dependency graphs. I believe Sixty's query-based architecture is capable of handling dependencies implicitly.

• Contrary to the intuition that comes with a background in traditional batch compilers, the "pipeline's" entry point is the query corresponding to the final pass (LLVMModule).

-- NB this code has been heavily modified for brevity!
compile :: ... -> Task Query ()
compile = do
  filePaths <- fetch Query.InputFiles
  moduleLLVMFiles <- forM (toList filePaths) \filePath -> do
    (moduleName@(Name.Module moduleNameText), _, _) <- fetch $ Query.ParsedFile filePath
    when printLowered do
      {- Debug printing logic omitted. -}

    llvmModule <- fetch $ Query.LLVMModule moduleName
    let llvmFileName = moduleAssemblyDir </> toS moduleNameText <.> "ll"
    liftIO $ Lazy.writeFile llvmFileName llvmModule
    pure llvmFileName

Name resolution

Name resolution occurs lazily, somewhere between the ModuleDefinitions and LambdaLiftedModuleDefinitions queries.