Computer Science

MickLH

12:19 AM

I'm sorry I had to deal with a rush of things just when it was getting interesting @Gilles

I am used to ChatJax if you'd prefer to use tex.

Gilles

@MickLH I'm still around, but not for long, it's pretty late here

MickLH

Oh ok

I'm shaky on the formal CS notation :(

I believe that my language semantics give the compiler freedom to almost arbitrarily wrap data in constructors

When a variable is declared as a value type, the compiler is allowed to promote it to a reference type silently

Does this map to the a = cons a a case or am I severely misunderstanding the concept?

Gilles

12:35 AM

@MickLH define “reference type” vs “value type”

MickLH

well I consider the "value type" strictly as data

whereas the "reference type" is strictly a valid pointer to a value type

I'm sorry for being so informal about such a topic

The existence of a reference implies that the value it references may not be deallocated, though it is mutable

Gilles

hmmm, silently converting from immutable to mutable is weird

but it's orthogonal to circularity

In a programming language, you can admit any circular definition. But it's nice to reject circular definitions that cause a loop at definition time.

A lazy language like Haskell can allow any circular definition, because a definition doesn't evaluate anything. In Haskell, let x = x is valid, and terminates. (But it isn't particularly useful; if the program ever tries to get the value of x, that loops forever.)

let x = x can be useful (in a lazy language) if you need to pass a value to a function, but it's difficult (perhaps impossible) to build a value of the right type, and you know that given the other arguments that you pass to the function it isn't going to use that argument.

MickLH

12:54 AM

That appears topologically similar to my situation with a data type containing a reference to its own type. Because all types are non-nullable unless otherwise specified, if I were to let it compile it generates working code but the initializer for the self-referential type recursively calls itself until memory is exhausted

There is another flavor in the mix, the "pointer type", which is identical to the ref. type except for one key detail: It can never legally escape the scope it was created in.

The actual pointer value itself is off limits, and in practice even atomically changes underneath you but you can never observe this because it always points to the correct object

If the pointer type is declared nullable though, it can now exit the scope legally, but can spontaneously become null at any moment

It's roughly equivalent to the C++ weak_ptr<>

So, what I'm trying to solve here is: What implications does this have on cyclical graph algorithms?

Oh, damn, the problem is still ambiguous because I haven't described the semantics I've imposed onto mutable and immutable types

Long story short with that topic, "immutable value types" are actually mutable values, but producing any observable side effect is illegal

It sounds asinine but it's useful (eg. Interval arithmetic expression that always represents some real number, but the interval itself can become tighter on request)

vzn

1:23 AM

@EvilJS saw that, luvd it, about as cool as cubestormer3!

@MickLH why do you want to design a (programming) language? that is a generally somewhat infrequent or rare activity...

MickLH

@vzn I've always found compilers interesting, I have a lot of ideas I enjoy experimenting with, and finally to address some shortcomings I perceive in existing languages I use

I'm obsessed with static analysis

vzn

1:39 AM

@MickLH ok. what "shortcoming(s)"? agreed most languages have them, but for any supposed "shortcoming" there is probably a language that doesnt have it...

static analysis maybe has some possibilities that havent been fully explored... seems to be a continuing area of research...

(re your SE profile) do you work on games?

MickLH

@vzn well there are many simple things I can infer from static analysis that I have to either code manually in C++ or pay for even when I don't use in C#

@vzn I do, that's the main thing I enjoy coding. Graphics especially

vzn

what languages are you using for gaming? agreed c++ datastuctures are an area of continuing evolution...

MickLH

I tend to like JavaScript or C++ depending on what I need to do

I'm not very fancy lol

vzn

@MickLH it sounds like maybe an API for some type of datastructure may be what youre aiming at... although virtually all the std ones already exist somewhere...

are you using any game APIs/ pkgs?

MickLH

I've worked with and ran into architectural problems with Cube2, Source, Unreal, Unity, and Leadwerks engines

vzn

1:47 AM

@MickLH and is that what you want to fix?

MickLH

The game I want to build is "too ambitious", or at least it was when I started almost a decade ago

vzn

this was also cited somewhat recently by R, maybe relevant

Domain-specific language

A domain-specific language (DSL) is a computer language specialized to a particular application domain. This is in contrast to a general-purpose language (GPL), which is broadly applicable across domains, and lacks specialized features for a particular domain. There are a wide variety of DSLs, ranging from widely used languages for common domains, such as HTML for web pages, down to languages used by only one or a few pieces of software, such as Emacs Lisp for GNU Emacs and XEmacs. DSLs can be further subdivided by the kind of language, and include domain-specific markup languages, domain-specific...

MickLH

My programming language project today is the spiritual offspring of my experimental C++ preprocessor, and my custom engine's DSL

I've flipped the situation around and am now using my own language to code the engine itself

The preprocessor experiments were geared towards implicit programming, one of the main features was performing algebraic manipulations over programs. I mean not limited to automatic calculus, but more like algorithmic complexity reduction

vzn

ok

MickLH

Things like setting up a recurrence relation that describes a loop, enumerating the possible implementations, and emitting an automatic dispatch between the sometimes-best candidates

Some trivial O(n) loops can of course be computed in O(1)

While some O(n) loops can be converted into algorithms that may be more complex, maybe O(n log n), but have significantly better constant factor or cache properties

An early prototype of the program once designed an O(n log n) algorithm that I had never thought of from some O(n^2) code I had typed

vzn

2:06 AM

this sounds a bit abstract for game design. odds are there is some game design "pattern" that suffices. but building new languages with new useful properties ofc will continue probably as long as there are computers...

MickLH

It is very far from the usual game design methodologies lol

But there are 2 good reasons for this: (1) My "dream game" is very far from the usual game design methodologies. (2) I have other use cases, like web browsers.

vzn

games do seem to be one of the leading, even cutting-edge areas of many types of code optimization... mostly rendering but many other related areas...

a "dream game" is different than a "dream game design"...

MickLH

My interest in game development is driven by specific game that I want to play

vzn

@MickLH namely?

MickLH

It's not a game that exists outside of my head

Though it does exist vividly inside my head, I can visualize it more clearly than I can remember what I saw just hours ago :P

Actually... it's starting to exist outside my head, there are several contributors onboard at this point, and about 10 years of R&D into it

vzn

2:15 AM

great, what language/ platform are you using?

MickLH

Up until some time last year, everyting was C++ / OpenGL

Now, new classes are written in my language

Everything has been prototyped already, all the components work, it's very exciting.

But mostly they are not efficient enough to build the full game on top of

vzn

@MickLH your actual performance area problem still sounds vague/ unidentified.

MickLH

There are several specific problems, to list a few examples: (I must give up on a representative example, just to start listing somewhere... so this is a lame example.) When high energy debris is produced by the physics engine, the large amount of very long collision geometries necessary for avoiding tunneling become prohibitively expensive

Even approximating each one as a cylinder, they simply touch too much data even just to confirm that they end up doing nothing, never mind the follow up action required for a significant number of them

On that issue, I'm trying a design based on binary search with heurestics to make the range smaller before searching

Besides specific roadblocks, there are also some issues where there is no clear "problem zone", like some of the lighting computations simply require many samples to look acceptable in areas of high frequency variation

(That stuff is not why I decided to design my own language though)

The stuff I want from the language is much, much simpler. A good example of a shortcoming I see in most languages is that remote procedure calls are cumbersome to setup and use. I've designed my language so that I can simply inform the compiler where I'd like the current scope to be executing. I can even move the current scope to a different execution context mid-block

The compiler can infer what variables must be saved into a closure, setup the lambda, enqueue the RPC, and setup the synchronization primitives when the return value is used

(that's what I thought, lol)

vzn

3:38 AM

@MickLH you want to track "debris" accurately? is that really necessary for gameplay?

@MickLH lighting is nice but extraneous to gameplay. and some lighting adjustments are expensive yet dont change the scene much. its a more subliminal effect on gameplay.

@MickLH agreed remote proc calls are not done well in some high level languages eg java, there has been a lot of evolution in this area.

games and gameplay involve numerous design/ computational tradeoffs of course. the "off-the-shelf" engines are very performant and finetuned/ optimized in most areas after even decades of optimization in some cases.

MickLH

3:55 AM

@vzn Lighting conditions and even debris are significant to achieve the gameplay I envision

Example: You should notice someone around a corner because of the light they block, even when they do not cast a direct shadow over your viewport

And debris is even more important to my game, the physics don't have to be perfect, but I need to approximate the conservation of volume

Bounty!

7:31 AM

0

Q: Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case Execution Time (WCET) analysis. I have gathered a short list of events, which I think are the contr...

Computer Science Meta

5:09 PM

1

Q: Confusing formatting of inline multiline TeX

This answer contains the following code: $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. Image: Because of the way this is rendered, it appears as if part of the...

bug mathjax

EvilJS

7:22 PM

@MickLH so what language are you creating? With VM? Static typed? I would like intro ;) This will be for personal use or publicly available? How do you optimize it? Do you write everything from scratch or connect backends? You have compiler? Interpreter or translator with preprocessing?

MickLH

@EvilJS Ok, for the basics: Strong static typing, C flavor syntax, no VM (yet?), I plan to release it publicly but I guess it's a personal project, optimization is its own huge topic, I mostly write things from scratch, I have mostly compilers but also a few interpreters

There are some important details though, so that above is misleading

One of the static types is a dynamic typed object

My compiler architecture has always been pretty standard: Text -> Token Array -> Syntax Tree -> Program Tree -> Output Code

Lets see... I do optimizations during the program tree phase, the language is designed to be straightforward to analyse. The definitions of things are specifically loose to facilitate that, for example code that you write is allowed to be run in any order that does not violate dependencies, including concurrently.

I am designing a VM (literally) right now. When that's designed I'll immediately flatten the program tree into bytecode, then do optimizations there

I actually did release an open-source interpreter a long time ago, but I've taken that down since

EvilJS

7:53 PM

@MickLH very cool. This VM is stack, register or hybrid? Do you intend to let your VM to run someones bytecode or every check of code is in compiler?

MickLH

I think it's hybrid but leaning towards stack... it's "immutable stack"

And I do intend for the bytecode to be accessible, but also all the code checking is in the compiler

So "both" on that, I guess they aren't mutually exclusive because bytecode describing an illegal program is allowed to fail horribly

This is a performance concern, because I'd like to eventually have runtime JIT optimization

And I don't want the JIT busy verifying validity of programs, as that would punish well designed programs for the sake of poor ones

In my wild fantasies I dream of my bytecode becoming a high-level complement to the LLVM project (as if my ambitions aren't already a bit over-the-top :P)

Today though, I have not even worked LLVM in yet, I'm just emitting a small subset of C because this gives me a debugger for free

EvilJS

I got stuck on optimization phase and JIT or optimal assembly per architecture

MickLH

I have spent so many hours on that exact question ;)

EvilJS

And trivial answer is - take LLVM backend - but this is just not the way I imagined ;)

MickLH

My conjecture so far is that the optimal assembly must be defined in terms of what you know about the program's execution, and so I would like eventually have a JIT which produces the optimal assembly

This way the runtime can establish "invariants" temporarily and recompile functions who's cumulative overhead outweighs the recompile cost

EvilJS

8:07 PM

Yeah, hotspot is cool, but even simpler - how to optimally use registers when you know what to do, or even got architecture available functions with cost in cycles.

MickLH

or.. expected cumulative overhead anyways, I've pretty much given up exact analysis and have aimed at a probabilistic definition of optimal at this point

EvilJS

The only working idea - I use annotations - so this is manual for now

MickLH

@EvilJS For these details, I assume that I can never predict the CPU that comes out tomorrow, and so my idea is to instrument representative code segments and try to measure these timings, but this is not implemented at all

I mean, I've left room for it in the design, but I currently just outsource debugger/profiler functionality to a C compiler

EvilJS

But you have VM deployed - this is the place (I assume) to cover. But I end up with difficulty there - bytecode has to be translated by VM :-/

MickLH

There is an interesting thing I have not mentioned at all, one of my "supported" target platforms is abstract and corresponds to a client-server connection

EvilJS

8:13 PM

So for now I split phases - internal language from "compiler" and deployed code gets additional translation phase. And now I am cheating - asm optimizer, not mine :-/

MickLH

@EvilJS It's not cheating! It's just being efficient with your time

I think this abstract "client-server-session" context thing has something to it, I've never seen it done before exactly the way I imagine. The closest thing I've seen is server languages that can automatically generate javascript post-backs

For it, I've implemented Javascript as a compile target, and PHP as a compile target

EvilJS

Oh, do you use PHP7 or maybe HipHop?

MickLH

I wrote it so long ago I was using PHP 5 at the time, but I made it compatible down to PHP 4

I only used PHP because it's so cheaply widely available on shared hosts

That mode is logically not ready for public consumption though, even if it were implemented fully and perfectly, I haven't designed annotations for labeling "secure" data

EvilJS

I have encountered problem with node.js - every thread made its execution and shall free the resource - for now it works only on paper. It never frees resources, being too busy executing next threads...

Does your VM use threads?

MickLH

Yes

There is a Thread instruction actually

EvilJS

8:21 PM

System threads? Or white/green ones? Oh, do you use instruction counter?

MickLH

Forgive my ignorance, let me do cursory research on "white/green" threads

Oh, they are "green-ish"

EvilJS

Well, you simulate threads, not system ones.

MickLH

It's a hybrid, usually it operates as simulated threads, but the VM is also multithreaded

It's sortof an automated thread pool situation

EvilJS

With counter - popular in books and available projects, but I never seen usage for it.

MickLH

But there is also support for system threads, I have invented a concept I call "thread blocks"

It's written like any other block in a C style language (ie. thread "Name" { ... })

If a name is provided though, then it uses the thread with that name, creating it if it does not exist

Then inside this context, one can use a primitive: yield thread; to explicitly cooperate in multitasking

This is part of my solution to remote procedure calls, for example when using OpenGL, one can create a "render thread" which is a thread block containing an infinite loop to do interactive rendering

Then in the appropriate place (in this case, right before causing the GPU driver to block on the command queue) one would yield the thread. Now anywhere in the code, you can use another thread block aimed at the same "render thread" to do things that require the thread-specific context

The block is scheduled and immediately proceeds to the next statement, but access to any variables the block may modify will block until their status is confirmed

(In practice, I simply generate a lambda with a closure, and add it to a queue)

EvilJS

8:54 PM

By hybrid I meant compiled libraries to run, stack for C extended functions and registers for the rest. If you generate closure - this covers a scope, so there are references and... There is stack/registers set per closure?

MickLH

9:20 PM

@EvilJS I've implemented mostly normal hardware stack stuff, but I've been experimenting with using the heap instead, as in scope objects

Transcript for