[gambit-list] Gambit compiler is deterministic right?

Marc Feeley feeley at iro.umontreal.ca
Fri Mar 15 07:47:52 EDT 2019


But what does it mean for the compiler to be deterministic?

- deterministic for different invocations of gsc, or for different calls of compile-file within the same invocation of gsc (gensym would only potentially be an issue in the second case)

- exact character comparison of generated .c file for a given Scheme file and its include dependencies

- same .c code generated regarless of file name and location in the filesystem (it is already not the case if the file names are different, and with -debug the location in the filesystem is an issue)

- same .c code for each top-level Scheme definition, but possibly not same ordering of those definitions

- same ordering of all the lines of .c code, but possibly different names for local labels, local variables, etc

- different ordering of the instructions in the code (i.e. ordering of labels), but same semantics

- same generated machine code from gcc for a given Scheme file

What is your use-case and which definition of compiler determinism are you looking for?

In my coding style I try to avoid nondeterministic behavior, but I have no proof that there isn’t some nondeterminism left.

Thread preemption interrupts are particularly nasty because they may cause continuations to be captured in subtly different ways, which can lead to the stack area overflowing sooner or later, which impacts when GCs are triggered, which impacts where objects are allocated, which affects the collisions in eq? hash tables, which affects the ordering of table->list (which is used in a couple places in the compiler, but fortunately it seems the resulting list is then explicitly sorted).  Anyway, you get the idea that it is non-trivial to prove the strictess level of deterministic behavior (exact same generated .c code).

Marc



> On Mar 15, 2019, at 1:02 AM, Adam <adam.mlmb at gmail.com> wrote:
> 
> Hi Marc,
> 
> I meant except for nondeterministic behavior caused by macros, so your example below is excluded from the definition.
> 
> The compiler uses gensym a lot, this would be a primary cause of nondeterminism wouldn't it, so for instance if thread-safe determinism would be desired, the Gambit user would need to implement a thread-local gensym, correct?
> 
> (This would exclude thread preemption interrupts and GC as sources of nondeterminism - thread preemption and GC would only effect |compile-file| in the way that it could affect the order of gensym calls, right?)
> 
> Oh hashtables as a source of |compile-file| nondeterminism, interesting - what does |compile-file| use hashtables for?
> 
> Thanks!!
> Adam
> 
> On Fri, 15 Mar 2019 at 12:55, Marc Feeley <feeley at iro.umontreal.ca> wrote:
> You’ll have to define what it means for the compiler to be deterministic.  Do you expect the compilation of the following program to yield the same executable every time it is compiled?
> 
> (define-macro (stamp)
>   (read-line (open-tcp-client "time-a.timefreq.bldrdoc.gov:37")))
> 
> (pp (string-append "hello! " (stamp)))
> 
> Macros open a big can of worms…
> 
> If you avoid macros the compiler is probably mostly deterministic… but I do not have a proof handy!  Hash tables, GC, thread preemption interrupts, etc can introduce nondeterminism that may be observable in some situations.
> 
> Marc
>  
> 
> On Tue, 26 Feb 2019 at 09:18, Adam <adam.mlmb at gmail.com> wrote:
> Hi Marc,
> 
> Gambit's compiler is deterministic right?
> 
> (As in Scheme to GVM, GVM to C or binary. Underlying C compiler's determinism is a separate matter altogether.)
> 
> A consideration could be that compilation output is a function of |gensym| and therefore its counter must be managed for deterministic compilation.
> 
> Another consideration that if running more instances of the compiler in one Gambit process concurrently, the |gensym| calls could have arbitrary order and therefore determinism break.
> 
> Adam
> 
> 	Virus-free. www.avg.com




More information about the Gambit-list mailing list