hylo-lang / hylo Goto Github PK

typeExpr parsing logic could be sunk into expr parsing and merged, rather than backtracking. That would be faster.

Attribute arguments should be parsed as expressions, so that we can write e.g.:

@align(MemoryLayout<Int64>.alignment())
public let n: Int16

See #83

Add a default access modifier (likely private) and synthesize it on all declaration when public is not explicitly supplied.

Metatype is a word, so t shouldn't be capitalized

We need a format to store/load modules that have been type checked, so that we don't have to recompile every sources.

That format should probably include the typed AST of the module's public API and its IR. Then importing a module would consist of injecting the AST in the program under compilation and merge its IR functions.

As I'm poking into the transpilation code, I'd like if each Program contained an (Optional) reference to its entry point, the main function.

Originally posted by @dabrahams in #68 (comment)

The def-use chain of a value is currently stored in that value. The issue with that approach is that it compels values to have reference semantics, so that their def-use chain can be updated whenever a new instruction is created.

If def-use chains were all stored in an external data structure owned by the module, we could give them pure value semantics. Further, the builder would no longer to allocate them in the shared buffer to guarantee uniqueness.

The interface of the function to type check expression currently expects expr to be inout, so that it may be substituted during type checking (e.g., to replace unresolved declaration references).

However, this choice can lead to an overlapping mutable access when we type check pattern bindings, if the initializer refers to the declaration itself, e.g., val x = x.
This situation is illegal and should be caught during name resolution.
Nonetheless, we should eliminate the possibility of an overlapping access.

The simplest solution is probably to change TypeChecker.check so that it returns the expression checked, along with the solver's solution.

These failures: https://github.com/val-lang/val/blob/96eb07bf89fbb9e92fe0147728562e787df5be7e/Tests/ValTests/CXXTests.swift#L39
https://github.com/val-lang/val/blob/96eb07bf89fbb9e92fe0147728562e787df5be7e/Tests/ValTests/CXXTests.swift#L46

Need to pass the file and line of the test cases to the file: and line: XCTAssert parameters, and pass the text of the diagnostics to as the message parameter.

Diagnostic logging looks really complicated to me and it appears to be coupled into the CLI, so I don't know how to do this job. But without it, test development is going to be really painful.

The generic environment of a declaration is responsible for tracking conformance and equivalence relationships on the generic type parameters associated with the declaration. We should also track relationships on associated types, so that we can handle situations where two views are defining the same abstract type.

view V {
  type A
  fun foo() -> A
}

view U {
  type A
  fun bar() -> A
}

// This function should type-check.
fun f<X where X: V, U>(x: X) {
  var a = x.foo()
  a = x.bar()
}

Gathering all relationships in the declaration's environment will also improve the efficiency of lookup requests on associated type. For instance, we'll be able to check the conformance table using X::A as a key rather than going through all of A's conformance and look for Self::A in every one of them.

For example, once type checking is complete, lookups in declTypes should never fail, so for example program.declTypes[someDeclID] should not produce an optional.

The options are:
raw-ast : gets you the AST right after the parser, in JSON
raw-ir : performs type checking and outputs the IR before borrow checking
ir : performs type checking and borrow checking, outputs the IR
llvm-ir : outputs LLVM IR
binary : outputs a library or executable (depends on the input)

Title says it all.

See also https://github.com/val-lang/val/pull/106/files#r1031891565

The AST implements Codable to get serialized as JSON:

valc --emit raw-ast -o main.json main.val

The resulting json file is barely usable by a human, though. It's just an array of quite shallow data structures. It would be interesting to transform that representation to something human-readable (in JSON or another format).

See hylo-lang/hylo-lang.github.io#11

Property maps notionally implement functions or… properties.

program.declTypes[valFunDecl]!

makes less sense than

program.declType[valFunDecl]!

It has no obvious meaning to a reader who hasn't seen it.
https://github.com/dabrahams/magoo/blob/main/Sources/SourceRegion.swift#L105 has a better alternative

This is a hack/workaround because we're not matching both the literal 'in' and the identifier pattern. Something should be done

Given the following program:

public fun main() {
  let x = 0
  var y = x
  let _ = x
}

the error message is:

error: use of consumed object

which is missing the source location of the error.

/Users/dave/src/val/Tests/ValTests/TypeCheckerTests.swift:43: error: -[ValTests.TypeCheckerTests testTypeChecker] : XCTAssertTrue failed - CallFunction: type checking succeeded, but expected failure
/Users/dave/src/val/Tests/ValTests/TypeCheckerTests.swift:53: error: -[ValTests.TypeCheckerTests testTypeChecker] : XCTAssertTrue failed - CallFunction: 3 unexpected diagnostic(s)

This doesn't tell me what example it failed on, or where the unexpected diagnostics appeared.

A postfix operator ^ would match the prefix operator suggested in #107

Instructions for archiving are here

This is a not an issue but a comment. As a user I find it confusing to require "&" in +=, but not in =. See the code below (I haven't been able to compile Val to verify the code, but from my understanding it's valid).

public fun main() {
  var length = 1
  length = 2
  &length += 2
}

I understand the difference is because = is not a function. But since both mutates value, I would expect they have the same syntax. Otherwise I'd have to stop to think if it's a = or a function when writing the code above. Also, since the language emphasizes mutable value, it would be great if it has a consistent syntax to help user to identify the places where a value is mutated. Just my thoughts, and feel free to close it if you don't agree.

Knowing the intent of the lookup request while it's being processed could be use to break dependency cycles gracefully and generate more precise error diagnostics.

Using @testable import makes it extremely easy to overlook things that were supposed to be public but were left internal. In general I try to isolate tests of internal components from the public ones for this reason.

See any of the https://github.com/loftware repositories for examples.

Test runners have a lot of code in common to execute the compiler pipeline. That includes the following files:

• Tests/ValTests/CXXTests.swift
• Tests/ValTests/EmitterTests.swift
• Tests/ValTests/ParserTests.swift
• Tests/ValTests/TypeCheckerTests.swift

This code should probably be factorized into a reusable driver.

The README.md instructions aren't sufficient to build Val on a Windows environment. It would be useful to support this environment to increase the pool of Val developers and confirm cross-platform support for the compiler and, eventually, standard libraries. This ticket is intended to track work towards this end.

Here are a few suggestions for getting started:

1. Decide on a Windows package manager for pulling in the Swift and libc++ dependencies. I'd suggest Chocolatey as this seems to have the largest community at the moment.
2. Create a package for the Windows Swift installer available here. Contribute this package to the community so it is widely available.
3. Build libc++ on Windows using clang+llvm following instructions available here.
4. Create a package for libc++ on Windows.
5. Troubleshoot and fix any issues that arise from running the swift .build/checkouts/LLVMSwift/utils/make-pkgconfig.swift command per the instructions.
6. Troubleshoot and fix any issues with building the compiler.
7. Update the README.md to indicate Windows support and provide its workflow.

The preliminary design allows for views to declare abstract types, which serve as placeholders in method and property requirements, and are expected to be "instantiated" in conforming types. They correspond to the concept of associated type in Swift.

Here is a "simple" example (syntax attempt). The view Container defines an abstract type Element that is used as a placeholder to specify the type of the mutable property element. To satisfy its conformance to Container, the product type IntBox declares a type alias that maps the name Element onto the concrete type Int.

view Container {
  type Element
  var element: Element
}

type IntBox: Container {
  type Element = Int
  var element: Int
}

One can specify bounds on the type that instantiate an abstract type. In the following example, the bound constrains conforming types to instantiate the abstract type Element with a type that conforms to Hashable.

view HashableContainer {
  type Element where Element Hashable
  var element: Element
}

Ideally, one should be able to specify any kind of type requirement, just as in the clause of a generic type.

view PairOfContainers {
  type Fst where Fst: Container
  type Snd where Snd: Container, Snd::Element == Fst::Element
}

public fun main() {
  let x: Int[2]
}

The parse sees two statements (i.e., let x: Int; [2]) instead of one (i.e., let x: Int[2]).

The job appears to be almost done; see this commit. The SansHint variants of those tests can then be eliminated.

Here are some observations/first-impressions I had of Val (just from the docs, hello world won't compile -> undefined name 'SourceRepresentable<Name>(value: print,...).

lets and sinks

• According to the docs, methods and member subscripts can have three overrides for let, inout, and sink. Since the decision to call the let or sink version depends on what you do after the callsite (whether or not the identifier passed into the method is used again), reasoning about local state becomes bizarrely non-linear and overly complicated. It would be nice to explicitly control overload-resolution at the callsite (e.g. via more modifiers to complement &).
• Coming from C++, the way sinks can 'steal' lets is hard to grapple with. In C++ terms, you are casting away the const from a const-ref then moving the resource, which would be a big red flag. I want to think of lets as captures (or caps :), not to be confused with closure/lambda captures) that grab onto a value, block access to the value from code that can't see the capture, and carry it around immutably until the capture dissolves in the scope where it was created (releasing the value back to a prior owner, or immediately destroying it). By introducing the possibility for lets to be 'emptied', you make non-local reasoning more difficult. Even though the compiler will prevent you from using a let that has been emptied, you have to memorize the implicit interface of a function in order to reason about it - i.e. the interface imposed by all downstream sinks that may only be discoverable with the compiler's help (e.g. when dealing with lets of non-trivial data structures; I can only tremor at the possibility of vectors full of holes; then again, maybe I am overestimating the power of sinks) (also, what happens when you are passing functors around? scary). While indirect partial-sinking may be an optimization (and hence a reason to have a let instead of a sink), it seems like the human cost is too high. I'd prefer if let -> sink always requires an explicit copy, and the compiler just recommends using a var, inout, or sink as input to a sink whenever a let -> sink copy appears superfluous. I realize this let/sink relationship is deeply embedded in the current design. Maybe the idea is users should just copy their local lets if a callee is sinking somewhere down the call stack, causing a compile error in the local function. However, what about cross-library interactions? It seems like one new sink in a tiny library function could propagate ABI-breaking changes throughout an entire ecosystem.
  • I could be completely misunderstanding this, hopefully can test stuff out if I get valc working.

Other comments (trivial syntax)

• Less is more: function labels. According to the docs, function labels are used for overload resolution to allow multiple same-name functions with the same parameter lists, and for syntactic sugar: "This feature can be used to create APIs that are clear and economical at the use site, especially for functions that accept multiple parameters:". I really appreciate naming parameters at the callsite, but labels seem like a step backward. Labels make it harder (relative to simple parameter names) to reason about a called function because when looking between the function and the callsite, you need to translate parameter names into callsite labels. Is it really important to add clutter in order to get more function overloads? As it is, function overloads are often overused and overloads with similar parameter lists can be a mess for humans to parse through.
• English is my brain's language: variable definitions. I really prefer seeing the type first. For example, var Double x = 5.0 translates to "define a variable-qualified Double named x and initialize it with value 5.0", whereas var x: Double = 5.0 translates to "define a variable named x that is a Double and initialize it with value 5.0". I don't want to know the name before I know the type, because the name is just a handle onto the real thing. The big exception is automatically-typed variables, which is probably a core motivation for the trailing type syntax (to omit auto). Personally, auto is a very short word that clearly expresses what's happening.
• Pythonization: opaqueness is frustrating. Using let to make variables may have a nice flow in isolation, but it feels really far away from 'what is the thing you are making/have, exactly?' Let is not a noun - it is a verb. Hence my earlier suggestion to use capture or cap instead :) (currently used for 'closure captures', which could be renamed to 'closure context variables', 'closure attachments', or something).
• My eyes are slow: optional omission of return. Fewer characters are required, but the tradeoff is extra effort to read code - to check whether or not a function has a trailing return type (not a simple effort for those disgusting functions with 300-character-long declarations, and also an effort for small functions). You lose important 'at a glance' pattern matching that comes with a mandatory return keyword (similarly with yield in subscripts).
• Multi-line statements: how does it work? How does the compiler figure out where the end of a statement is, if a statement is spread across multiple lines (which may be ergonomically necessary for beefy statements)? Similarly, how does the code reviewer easily identify where statements end (for example, in multi-statement multi-line arithmetic)?

Instructions: https://www.cds.caltech.edu/~mhucka/blog/posts/2020-07-19/renaming-your-master-branch-in-git/
Reasoning: https://www.cnet.com/tech/computing/microsofts-github-is-removing-coding-terms-like-master-and-slave/

Perhaps cause would be better than because.

Also, from a #106 (comment):

FWIW, x and y would be better than left/right, because it's a symmetric relation and handedness is irrelevant.

I tried running valc with no arguments to see what would happen:

Error: Missing expected argument '<inputs> ...'

USAGE: cli [--emit <emit>] [--modules] [--nostdlib] [-o <o>] [--verbose] [<inputs> ...]

Shouldn't the cli instead be valc?

The val repo doesn't contain any example Val programs. They should be added.

I found this to be a pleasure to use and it
reduced the amount of code in my project considerably over the corresponding
hand-coded parser.

The last line of README.md code example shouldn't be

print(foo.fst)

?

Does the precision adds anything useful to the reader?

Absolutely, yes.

What you wrote is wrong

Which goes to show that I don't understand the abstraction being documented here.

Originally posted by @dabrahams in #83 (comment)

I think this should be a static member in an extension of TypeProtocol, neh?

Originally posted by @dabrahams in #107 (comment)

During type checking, the AST must be piped through methods along with a set of other data structures (mostly property maps) that get updated throughout the process. It would be beneficial to wrap these data into a single abstraction, similar to TypedProgram.

Doing so, we could get rid of ScopeHierarchy so that requests about the lexical structure of the program can be handled by a single abstraction, rather than having either the AST or the scope hierarchy require access to the other.

/Users/dave/src/val/Sources/Driver/Driver.swift:110: error: -[ValTests.ValTests testEval] : failed: caught error: "moduleNotFound(moduleName: "Val")"

Seems like this indicates something might need to go into "/opt/local/lib/val"? Just guessing here.

Minimal example

fun f() {}
fun g() {
  f(x: 0) 
}

The error is caused by the way constraints for a function call are solved. The above program will create the following constraints:

τf == () -> ()
τf == (x: τ0) -> τ1
τ2 <: τ0
τ2 ⊏ ExpressibleByIntLiteral

Because the number of parameters do not match, the solver won't create any additional constraint on τ0 when it solves τf == (x: τ0) -> τ1. Hence, it will eventually have to solve τ2 <: τ0 by guessing τ2 == τ0, causing τ0 to be bound to Int.

As a result, trying to reify (x: τ0) -> τ1 will violate FunType's invariant, as τ0 won't be bound to a parameter type.

A name (Sources/Compiler/AST/Name.swift) is a value that uniquely identifies a single entity in a given scope. It consists of

• a stem (or base name),
• an array of labels,
• an operator notation (optional), and
• an implement introducer (optional)

For example, foo(a:b:).sink is a name whose stem is foo, the labels are a, b and the introducer is sink. infix+(_:) is another name whose stem is infix, the labels are two nil values and the notation is infix.

Unfortunately, the term "name" is used rather inconsistently in the code.

In declaration nodes:

AST nodes representing declarations parsed from source files often have an identifier property that describe the stem of some name. This property should be called stem to better describe its role.

In SingleEntityDecl:

Declarations that introduce a single entity conform to SingleEntityDecl, which requires a property name. That property is typed as String, but should be typed by Name instead.

Note: It shouldn't be SourceRepresentable<Name> because the name's value is not necessarily source representable. Only the stem is.

In the type checker:

There is a family of lookup methods in TypeChecker that accept a parameter name which should be called stem instead, to better describe its role (note: the first phase of name lookup ignores labels, notations and introducers).

The method TypeChecker.resolve should accept a name rather than its individual parts.

These Index types do not function like indices in a collection; they can't be advanced, etc. They are more like keys in a dictionary, but why not just call them IDs?

./valc fac.val

Undefined symbols for architecture arm64:
  "_P3IntO5infix3u2a21_a", referenced from:
      l_F9factorial21_a in main.o
  "_P3IntO5infix3u2d21_a", referenced from:
      l_F9factorial21_a in main.o
  "_P3IntO5infix3u3c21_a", referenced from:
      l_F9factorial21_a in main.o
ld: symbol(s) not found for architecture arm64

Most programs used to test the type checker use a programmatically built AST (e.g., TypeCheckerTests.testTraitDecl). That makes test cases hard to read, update, and maintain.

It would be preferable if those test cases generated ASTs from actual Val code using the parser.