zetah11 / zippy

a smol functional/imperative programming language
MIT License
2 stars 0 forks source link

how to handle unknown numbers? #23

Closed zetah11 closed 1 year ago

zetah11 commented 1 year ago

With the introduction of arbitrary expressions in range types, the backend may no longer know the size of such a type if partial evaluation is disabled. For some expressions, the type is enough (e.g. a range type 0 upto x where x: 0 upto 10 is at most 0 upto 9) but for something like 0 upto 2 * 10 the expression 2 * 10 has the internal type number, which, semantically, is an unbounded, arbitrary precision number.

This is problematic because there's no native support for such a type. Bytes, integers, and even >64 bit types can be stack allocated, but unbounded arbitrary precision types are usually implemented with dynamic allocations. As a start, I'll probably just say "number is whatever large integer that works best", so like long long on C.

The basic problem is that I want any program that compiles with partial evaluation to compile without. The partial evaluator has the advantage of always using arbitrary precision numbers, something the backend might not.

zetah11 commented 1 year ago

I think a decent approach, at least for now, will be to require partial evaluation on types at least for the native backend. I could later add a bytecode backend that supports arbitrary precision numbers that can be used when partial evaluation is disabled.

zetah11 commented 1 year ago

One thing to note is that the type number will probably only ever show up in very simple non-recursive expressions. If the user wants to write something like

let f x = f x

you need to give it an explicit type, which makes it easy to compute the largest possible bounds. But if the user writes

type T = 0 upto 2 + 4

then the expression 2 + 4 has the type number but it is (almost trivially) evaluatable. Basically, I think an expression will only get the type number if it does not reference other names. Perhaps an approach where only those values of type number are evaluated is a possible way to go that evaluates even less than the types-only approach?

zetah11 commented 1 year ago

Sketch of a general plan to resolve this in the C backend:

error [EC00]: unable to statically determine the range bound
 1 | type T = 0 upto (x => x) 5
                     ^^^^^^^^^^
help: move the expression to a top-level binding: `let bound: <some type> = ...`
zetah11 commented 1 year ago

Closing for now because the above approach was implemented. Arguably it's not perfect, but I think the only real alternative is to fallback to a native int width or something for number and work with that, but I don't like that.