search

basilTeam / basil

Fast and flexible language exploring partial evaluation, context-sensitive parsing, and metaprogramming. Compiles JIT or AOT to native code.
BSD 3-Clause "New" or "Revised" License
124 stars 11 forks source link

Thoughts about a flexible yet compile-time turing complete language #19

Closed dumblob closed 3 years ago

dumblob commented 3 years ago

Crazy braindump:

Today I opened again the repo https://github.com/zeroflag/punyforth and it triggered unexpected brainstorming.

What if Basil became a language with something like punyforth's goodies:

  1. the "dictionary" semantics (hyper static global environment)
  2. the unique exception handling
  3. the seamless yet clear distinction between "immediate words" (executed in compile time; suitable for metaprogramming - especially control structures and similar), "parsing words" (also compile time; suitable for metaprogramming by "looking ahead"), "deferred words" (executed in run time; copy-on-write for keys & values in the "dictionary"), "overriding" (executed in run time; suitable for aliasing and thus redefinitions or value changes etc.), and "quotations" ("recorded code in run time to execute in run time")
  4. terse syntax due to missing need for variables (but with dead-easy way to have them for clarity - e.g. by deferred words or overriding)
  5. unit testing etc.
  6. seamless cooperative multitasking

but would significantly improve on:

  1. syntax to become (much) better and ordinary
    1. the need of low-level manual shuffling with dup swap etc. is a no-go
    2. it shall support "stateful" code writing - most languages have some form of lexical scoping (delimited e.g. by a file beginning and end) in which one doesn't have to write some "prefix" etc. significantly lowering the length of combinators/methods/function_names/variable_names/etc.
    3. if possible all 3 notation variants shall be supported seamlessly (prefix, infix, postfix)
  2. performance to become (much) better on modern CPUs (stack is the bottleneck, low-level orientation is also a bottleneck, etc.)
  3. compile-time safety checking (including safer defaults and higher-level APIs & concepts)

No. (1) is already on its way in Basil, but compile-time stuff is not yet smooth enough and it doesn't seem as universal as ponyforth. With others, it's still an open question :wink:.

Thoughts?

elucent commented 3 years ago

Finally writing up a response to this...I think Basil's approach is fundamentally different to that which can be achieved in a super-low-level language like a Forth, but should ideally achieve the same ends. The main thing is that while small Forth-like languages can get away with sort of reductive semantics (a global unscoped dictionary for definitions is graceful but also doesn't scale great...), Basil is more targeted at users of existing languages and aims for high performance - this means, among other things, clear lexical scope and static type checking.

The solution Basil adopts to the above problems, of course, is simply to permit a highly dynamic "meta-language" confined to compile-time evaluation - we can do crazy things (albeit not really any more crazy than the average Lisp dialect...) and as long as we resolve them all in advance we shouldn't incur a runtime cost. As you mentioned, Basil already achieves point 1. (much more so in recent iterations than before, IMO) pretty decently, but by ensuring that no metaprogramming or dynamic code reaches the actual binary, performance should remain quite competitive - achieving point 2 (there's really no reason, besides compiler backend quality, why Basil couldn't compete with OCaml or even C++ in terms of generated code performance).

Point 3 is a little less explored in the current Basil iteration. In theory, the compile-time environment is turing-complete and quite powerful - it's essentially a Lisp interpreter, and with some caveats it supports a superset of Basil's runtime functionality. The issue with this is that Basil's current compile-time evaluation is quite slow, so to avoid overdoing compile-time evaluation we automatically lower any code that crosses a fairly small operation-count threshold. This is good for making sure we still compile expensive benchmarks, even if they aren't effectful, but it's kind of bad for sophisticated compile-time analyses and assertions. I think a good solution would simply be to allow "explicit comptime" blocks - this would be a built-in function that would evaluate its arguments without any compile-time profiling and auto-lowering. We could permit certain stateful and effectful functions, such as mutation and IO, at compile-time within such a block. With that, the user essentially has the full extent of the language's semantics available to express whatever ahead-of-time constraints or transformations they want. :)

Closing this since it doesn't really pertain to a particular feature. But we'll probably be exploring explicit compile-time blocks in the near future.

dumblob commented 3 years ago

But we'll probably be exploring explicit compile-time blocks in the near future.

That makes sense. But from my experience only if the blocks can apply to as small parts as one lexeme/token (any token at any place!). I.e. I tend to imagine the "block" as something enclosed in [ ] (as in Tcl, Til, etc.) or as just some prefix for an arbitrary lexeme/token. IDK.