Announcing the Voodoo Programming Language
Robbert Haarman
The time has come for me to announce one of my programming language
efforts. Dubbed Voodoo, it is a low-level language, providing just a
thin abstraction layer around the platform's instruction set and calling
conventions. The idea is that, rather than every language implementation
having to include code generators for all platforms it supports,
language implementations can use Voodoo as their back end, and the
effort of supporting and optimizing for multiple platforms can be
concentrated in Voodoo.
As such, the design goals for Voodoo have been:
- To provide an interface that abstracts away the specific instruction
set and calling conventions of target platforms.
- To impose as little of its own constructs on programs as possible, to
allow programs to be as efficient as possible.
- To be small and simple to implement.
Currently, there is a first set up for a specification of the language,
and a crude implementation for x86 (tested on Debian GNU/Linux).
Goals for the future include:
- Completing the specification and the implementation.
- Creating implementations for other target platforms (the first ones
on my list are Linux/MIPS and Linux/x86-64).
- Creating a way to query the features of the target platform (e.g.
bits per word, floating point capabilities, etc.)
- Creating a library that allows code to be compiled, loaded, and
executed on the fly.
and, last but not least:
- Creating language implementations that target Voodoo.
I invite you all to visit the Voodoo website at
http://inglorion.net/documents/designs/voodoo/
Comments are welcome, and any help in reaching the goals above would be
greatly appreciated, of course. Also, I would be honored if you used
Voodoo in one of your own programming language implementations.
Regards,
Bob
--
The only thing you know for sure is that you never know anything for sure.
thomas...@gmx.at
wrote:
> Greetings, friends!
>
> The time has come for me to announce one of my programming language
> efforts. Dubbed Voodoo, it is a low-level language, providing just a
> thin abstraction layer around the platform's instruction set and calling
> conventions.
Different calling conventions are IMHO only a problem under Windows.
> The idea is that, rather than every language implementation
> having to include code generators for all platforms it supports,
> language implementations can use Voodoo as their back end, and the
> effort of supporting and optimizing for multiple platforms can be
> concentrated in Voodoo.
>
> As such, the design goals for Voodoo have been:
>
> - To provide an interface that abstracts away the specific instruction
> set and calling conventions of target platforms.
>
> - To impose as little of its own constructs on programs as possible, to
> allow programs to be as efficient as possible.
>
> - To be small and simple to implement.
I don't want to discourage you, but there exists a language which
already comes close to your design goals. It is called C.
What makes Voodoo better suited as low-level language then C,
which also provides just a thin abstraction layer around the
platform's instruction set?
The Seed7 compiler creates a C program and calls an available C
compiler (gcc, cl from MSVC or bcc32 from BDS) to create object code
and to link afterwards. Several defines, macros and driver libraries
are used to compensate differences of the compilers, system librarys
and operating systems.
What would be the advantage of using Voodoo instead of C?
> Currently, there is a first set up for a specification of the language,
> and a crude implementation for x86 (tested on Debian GNU/Linux).
>
> Goals for the future include:
>
> - Completing the specification and the implementation.
>
> - Creating implementations for other target platforms (the first ones
> on my list are Linux/MIPS and Linux/x86-64).
Good luck. I guess this will take some time, especially when your
compiler will do optimisations.
> - Creating a way to query the features of the target platform (e.g.
> bits per word, floating point capabilities, etc.)
C does such things with defines. A feature test script such as
configure or some tests in the makefiles can generate a version.h
file which contains defines for the different features.
> - Creating a library that allows code to be compiled, loaded, and
> executed on the fly.
This sounds interesting. For such a thing C relies on operating
system features.
Greetings Thomas Mertes
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
Robbert Haarman
Thank you for your comments.
On Tue, Jan 06, 2009 at 10:25:35AM -0800, thomas...@gmx.at wrote:
>
> Different calling conventions are IMHO only a problem under Windows.
I can tell you that Linux/x86 and Linux/powerpc have radically different
calling conventions! ;-)
> I don't want to discourage you, but there exists a language which
> already comes close to your design goals. It is called C.
Indeed. And, of course, I've considered just using C as a compilation
target for my programming languages. However, C has at least one
important shortcoming: there are no guarantees about the memory usage of
tail calls.
This has been a stumbling block for me, as I like my languages to have
proper tail calls, so that tail recursion can be performed in constant
space. This allows recursive implementation of many algorithms that
would otherwise have to be translated to loops.
Proper tail calls are quite easy to implement in any assembly language I
have ever used, but tricky to express in C. There are various techniques
that can be used, but none of them are as elegant as simply having
guaranteed proper tail calls or low-level primitives to implement them.
> What makes Voodoo better suited as low-level language then C,
> which also provides just a thin abstraction layer around the
> platform's instruction set?
As stated above, C does not provide for an elegant way to code proper
tail calls. Voodoo does. That's one advantage.
Also, C is much more than a thin abstraction layer around the platform's
instruction set. Some of that may be functionality or features that
Voodoo currently lacks, but there are also parts of C that simply aren't
needed for the purpose Voodoo has been created for. All in all, Voodoo
is a simpler and smaller language, and therefore easier and quicker to
implement for new platforms.
> The Seed7 compiler creates a C program and calls an available C
> compiler (gcc, cl from MSVC or bcc32 from BDS) to create object code
> and to link afterwards. Several defines, macros and driver libraries
> are used to compensate differences of the compilers, system librarys
> and operating systems.
>
> What would be the advantage of using Voodoo instead of C?
Ideally:
1. No need for you (as author of the Seed7 compiler) to write as much
glue code to account for differences in lower level compilers. I am sure
not all complexity can be eliminated here, but I have some ideas that
may help. One is to provide a programming interface to Voodoo; think of
it as a library you can link to to get the Voodoo code generator into
your program.
2. No need for a dependency as heavyweight as the development software
you have mentioned. One of the goals of Voodoo is to be small and easy
to implement.
3. Once implemented, the ability to create and run code on the fly.
Unless I decide that this functionality does not belong in Voodoo, but
rather in a higher level library.
> > - Creating a way to query the features of the target platform (e.g.
> > bits per word, floating point capabilities, etc.)
>
> C does such things with defines. A feature test script such as
> configure or some tests in the makefiles can generate a version.h
> file which contains defines for the different features.
Yes. The idea is to have this two ways in Voodoo:
1. You will be able to query the features of the Voodoo implementation
through the library interface and through an external program. At least
the interface of that program will be standardized, so that there will
be a standard way to query features across Voodoo implementations.
2. There will be a standardized way to give additional guidance to the
Voodoo implementation, possibly including implementation-dependent
hints. I am thinking something along the lines of Common Lisp's
declarations: some standardized features an implementation may support
(and possibly some that are mandatory), and defined semantics for hints
that aren't recognized by the implementation that encounters them.
> > - Creating a library that allows code to be compiled, loaded, and
> > executed on the fly.
>
> This sounds interesting. For such a thing C relies on operating
> system features.
Yes. Obviously, I want to standardize this accross platforms, so that
you, as a language implementor, only have to code the feature once.
Thanks again for your comments and encouragement.
Regards,
Bob
--
When the blind lead the blind they will both fall over the cliff.
-- Chinese proverb
Harold Aptroot
news:afd67a3d-8c28-4365...@w1g2000prm.googlegroups.com...
> On 6 Jan., 18:45, Robbert Haarman <comp.lang.m...@inglorion.net>
> wrote:
>> Greetings, friends!
>>
>> The time has come for me to announce one of my programming language
>> efforts. Dubbed Voodoo, it is a low-level language, providing just a
>> thin abstraction layer around the platform's instruction set and calling
>> conventions.
>
> Different calling conventions are IMHO only a problem under Windows.
>
How about Linux x64? It isn't exactly rare anymore these days.
(snipped rest since it's mightly long)
Reinder Verlinde
Robbert Haarman <comp.la...@inglorion.net> wrote:
> The time has come for me to announce one of my programming language
> efforts. Dubbed Voodoo, it is a low-level language, providing just a
> thin abstraction layer around the platform's instruction set and calling
> conventions. The idea is that, rather than every language implementation
> having to include code generators for all platforms it supports,
> language implementations can use Voodoo as their back end, and the
> effort of supporting and optimizing for multiple platforms can be
> concentrated in Voodoo.
Good luck, but my money is on LLVM (<http://llvm.org/>) to play that
role.
The only feature you mention that LLVM is not aiming for is "To be small
and simple to implement"
And yes, it does appear to support tail calls. See
<http://llvm.org/demo/index.cgi>
Given the commercial backing that LLVM appears to have (both Adobe and
Apple seem to invest heavily into it), I expect that that 'simple to
implement' will not matter much. That would leave you with the 'small'
part as your major advantage.
Reinder
Crushed_Ice
language was a substitution for the total entropy in the system, rather than
approaching the problem at the details. Say for example you were designing
the language I wrote. You come at the issue say, "What about bologna
sandwiches?" At this point you wtite the instructions for the bologna
sandwich class. Attributes are bread, bologna, musttard, and pickles...
Now I write any global variables, such as time of bologna sandwich..
I usually spend the day with the language team, in our computer laboratory.
Our invention process is called transposition, which means reconstitution
from a solid idea denoted from general principles. The language performs in
the some way that that coffee machine works in the television series "Lost
In Space". You just say "hot coffee" to the coffee machine, and the coffee
machine knows that you mean "coffee", and not "cream of wheat cereal"! But
the coffee is aready in the machine. It doesn't have to be compiled like C
language usually requires. Unless you have an interpretative C compiler,
but then if you use that its not a new language because an interpretative
compiler is a compiled version of the original language which it interprets
after the fact..
Another example suited to this problem is the gymnastic tumbler, during an
earthquake. If he goes to the right, he may land on his head, so he
switches to his left foot which makes the problem go away!
<thomas...@gmx.at> wrote in message
news:afd67a3d-8c28-4365...@w1g2000prm.googlegroups.com...
James Harris
...
> As such, the design goals for Voodoo have been:
>
> - To provide an interface that abstracts away the specific instruction
> set and calling conventions of target platforms.
>
> - To impose as little of its own constructs on programs as possible, to
> allow programs to be as efficient as possible.
>
> - To be small and simple to implement.
Nice one Bob. I'm impressed that the documentation can be so succinct
and to the point. Something we should all strive for.
>
> Currently, there is a first set up for a specification of the language,
> and a crude implementation for x86 (tested on Debian GNU/Linux).
Some things I'm not sure you provide that may be needed:
Multiple return values from functions.
Data size options - 8, 16, 32, 64 bit.
Bit manipulation.
Booleans. Short-circuit booleans.
I haven't downloaded it as yet. Maybe you already provide these.
James
Mike Austin
implement continuations, exceptions and coroutines easily, but above LLVM
dealing with registers. The JVM and CLR can't do this because they're tied
heavily to stack operations.
Is this something Voodoo is targeting?
Robbert Haarman
Thank you for your comments!
On Tue, Jan 06, 2009 at 03:09:28PM -0800, James Harris wrote:
>
> Nice one Bob. I'm impressed that the documentation can be so succinct
> and to the point. Something we should all strive for.
I am glad you like it!
> Some things I'm not sure you provide that may be needed:
>
> Multiple return values from functions.
I have no plans to implement this. In my opinion, it is easy enough to
implement this on top of the existing mechanism with acceptable
performance. The ABIs I know do not provide for multiple return values,
either.
> Data size options - 8, 16, 32, 64 bit.
>
> Bit manipulation.
These are currently missing features. They will have to be added at some
point. Unsigned numbers probably fall in the same category. I also plan
to implement arithmetic operators such as divmod (yielding both the
quotient and the remainder) and a multiplication operation that yields a
low and a high word of the result.
Eventually, I also plan to come up with a mechanism for dealing with
arithmetic overflow, so that you can, for example, write efficient code
that performs arithmetic on fixnums, but upgrades them to bignums when
needed.
> Booleans. Short-circuit booleans.
I don't think there is a lot left to be implemented for those. Keep in
mind that Voodoo doesn't have any notion of types. It will let you
access local variables and memory locations, but it's up to you to
decide on a representation and semantics for the types of your
programming language.
What I do intend to implement is a few more variants of if. Currently,
there is only one that tests if a value is nonzero; there should also be
a test for zero and comparisons of two values.
Regards,
Bob
--
TODO
- Make TODO list
Robbert Haarman
> It would be really nice to see a language just below C - where you could
> implement continuations, exceptions and coroutines easily, but above LLVM
> dealing with registers. The JVM and CLR can't do this because they're tied
> heavily to stack operations.
>
> Is this something Voodoo is targeting?
Part of the reason I've created Voodoo is indeed that C, JVM, and CLR
are all too tightly wed to a specific model of computation. They all
provide constructs to support their model of computation, but these
constructs often get in the way when you are trying to implement a
language that has a different model. With Voodoo, I have tried to keep
that to a minimum. The idea is for Voodoo to provide just enough
abstraction to provide portability across platforms, but to otherwise
leave you free to use the raw capabilities of the platform as you see
fit.
Voodoo provides functions and local variables, simply because most
languages will want these, and I have not managed to think of portable
lower level primitives that could be used to implement them. I have
tried to make them as inobtrusive as possible; for example, functions
come with their own call frames, but call frames can be re-used. This
allows Voodoo's functions to support proper tail calls, unlike functions
in many other languages. If Voodoo's functions still get in the way, you
can always use goto. Speaking of which, I should probably add actions
that store the current instruction pointer and/or jump to a location and
store the old location.
As for the examples you mentioned (continuations, exceptions, and
coroutines): they are definitely concepts that are above the level of
Voodoo. I don't know if that is a Good Thing or a Bad Thing. I hope that
it will be possible to efficiently express them in terms of Vooodoo,
but, if not, it is possible that Voodoo will have to be extended.
Continuations, for example, could be implemented by transforming a
program to continuation passing style (functions take a continuation
function as one of their arguments; instead of returning, they call that
function). This would work (thanks to proper tail calls), but I don't
know if it is the best option. Another option would be to keep the
program in its regular form (A normal form, for Voodoo) and have
call-with-current-continuation copy the stack. However, Voodoo currently
provides no support for this.
Finally, I must admit that I don't know LLVM very well, so it is hard
for me to say how Voodoo compares to it. From what I have seen, however,
LLVM is much heavier than what I intend Voodoo to be; not just the
actual implementation, but also the feature set. I want Voodoo to be
lightweight, not just to facilitate implementation and help it spread,
but also so that it can be used in small language implementations. As
such, I think Voodoo and LLVM occupy different niches.
Thank you for your interest. Kind regards,
Bob
--
> Those who do not study history are doomed to repeat it
Yes, and those who do study history are doomed to watch in frustration
as it is unwittingly repeated by those who do not :-)
-- jonadab on Slashdot
Mike Austin
If they can be implemented easily in Voodoo, that's all I care about. You talk
about functions coming with their own call frame, or using goto - can you
create your own call frames, or ensure they're around until explicitly deleted?
> Continuations, for example, could be implemented by transforming a
> program to continuation passing style (functions take a continuation
> function as one of their arguments; instead of returning, they call that
> function). This would work (thanks to proper tail calls), but I don't
> know if it is the best option. Another option would be to keep the
> program in its regular form (A normal form, for Voodoo) and have
> call-with-current-continuation copy the stack. However, Voodoo currently
> provides no support for this.
Maybe this answers my question above, but I'll still ask. :)
> Finally, I must admit that I don't know LLVM very well, so it is hard
> for me to say how Voodoo compares to it. From what I have seen, however,
> LLVM is much heavier than what I intend Voodoo to be; not just the
> actual implementation, but also the feature set. I want Voodoo to be
> lightweight, not just to facilitate implementation and help it spread,
> but also so that it can be used in small language implementations. As
> such, I think Voodoo and LLVM occupy different niches.
>
> Thank you for your interest. Kind regards,
>
> Bob
Ahh, implemented in Ruby, nice. Not an optimization, but this could make your
code a little shorter:
@generator.send(action.to_sym, *args);
instead of:
case action
when 'import'
@generator.import *args
when 'int'
@generator.int *args
Might not work in every case though.
Sometimes I forget how much optimization goes into languages (looking at your
CodeGenerator#sub), and I am grateful for not having to do it. :)
Mike
Robbert Haarman
On Tue, Jan 06, 2009 at 11:05:25PM -0800, Mike Austin wrote:
> >As for the examples you mentioned (continuations, exceptions, and
> >coroutines): they are definitely concepts that are above the level of
> >Voodoo. I don't know if that is a Good Thing or a Bad Thing. I hope that
> >it will be possible to efficiently express them in terms of Vooodoo,
> >but, if not, it is possible that Voodoo will have to be extended.
>
> If they can be implemented easily in Voodoo, that's all I care about. You
> talk about functions coming with their own call frame, or using goto - can
> you create your own call frames, or ensure they're around until explicitly
> deleted?
No, but the idea sounds interesting. If we can somehow decompose
function calls into reusable parts, that would be great. Do you have any
ideas about how this could work?
> Ahh, implemented in Ruby, nice. Not an optimization, but this could make
> your code a little shorter:
>
> @generator.send(action.to_sym, *args);
Yes, you are right. I knew I could do that, but, for some reason,
decided not to. However, seeing the great uniformity of the code, I
think it would be good to refactor it. This will save a lot of code,
especially once more actions are added.
> Sometimes I forget how much optimization goes into languages (looking at
> your CodeGenerator#sub), and I am grateful for not having to do it. :)
That's the idea: you map your program to operations on words in memory
and variables, and then Voodoo does what it can to convert those to
efficient machine code. Perhaps not the most efficient machine code
possible, but pretty good for you not having to learn the instruction
set of any of the targets that Voodoo support, let alone worry about
calling conventions, alignment, pipelining, register allocation, etc.
Regards,
Bob
--
This sentence no verb
Robbert Haarman
http://inglorion.net/documents/designs/voodoo/, fixing errors in the
HTML and integrating it with the rest of my website. I've also added
links to and descriptions of some related work, such as LLVM and
Alchemist.
Regards,
Bob
Bartc
"Robbert Haarman" <comp.la...@inglorion.net> wrote in message
news:20090107084...@morgenes.inglorion.net...
You've also added a background rendering it almost unreadable!
I'm still confused as to where this language fits, between say C and x86
code.
If it's a thin layer over asm, then I would expect to have control over
registers, stack and so on.
And to have available all the datatypes (meaning lengths), typically 8,16,32
and probably 64 bits, as well as access to floating point.
Also, it would be useful to break through to the underlaying asm code where
necessary.
It's not clear also whether the expressions it mentions are compile-time or
runtime ones. And if runtime, where exactly are they elaborated, and what
operator precedences are (if that is meaningful). An example beyond
HelloWorld would be useful:
if I have an external (C?) function sum(int,int), and I have int variables
in voodoo called x,y and z, what would the call sum(x,y+z) look like? How in
fact do you tell it how parameters are passed (left to right, right to left,
stack or register, etc)?
--
Bartc
Robbert Haarman
Thank you for your interest in Voodoo.
> "Robbert Haarman" <comp.la...@inglorion.net> wrote in message
> news:20090107084...@morgenes.inglorion.net...
> >I've updated the Voodoo webpage at
> >http://inglorion.net/documents/designs/voodoo/, fixing errors in the
> >HTML and integrating it with the rest of my website. I've also added
> >links to and descriptions of some related work, such as LLVM and
> >Alchemist.
>
> You've also added a background rendering it almost unreadable!
My apologies. This is a bug in Internet Explorer I thought I had
implemented a workaround for, but apparently I hadn't. I have done so
now, and added a friendly nag message. ;-)
> I'm still confused as to where this language fits, between say C and x86
> code.
Voodoo is indeed somewhere in between. The presense of functions, local
variables, and a control structure (if) make it close to the level of C,
but C has many things that Voodoo doesn't: type checking, loops, nested
expressions, a standard library, and more. This is fully intentional:
Voodoo is not intended to be a high level programming language, but only
to abstract a target platform's instruction set and calling conventions.
Voodoo is meant to be an intermediate step to native code generation,
not a language intended for writing applications in directly.
> If it's a thin layer over asm, then I would expect to have control over
> registers, stack and so on.
Voodoo will not give you direct access to the registers, as that would
expose details of the target platform that Voodoo is intended to
abstract away.
Of course, it is possible that some Voodoo implementations will give you
access to platform specifics as an extension.
> And to have available all the datatypes (meaning lengths), typically
> 8,16,32 and probably 64 bits, as well as access to floating point.
These are planned for future versions.
> Also, it would be useful to break through to the underlaying asm code where
> necessary.
Yes. There may be some standardized method for this at some point.
> It's not clear also whether the expressions it mentions are compile-time or
> runtime ones. And if runtime, where exactly are they elaborated, and what
> operator precedences are (if that is meaningful). An example beyond
> HelloWorld would be useful:
>
> if I have an external (C?) function sum(int,int), and I have int variables
> in voodoo called x,y and z, what would the call sum(x,y+z) look like? How
> in fact do you tell it how parameters are passed (left to right, right to
> left, stack or register, etc)?
In Voodoo, sum(x, y + z) could be rendered as:
let tmp add y z
call sum x tmp
You cannot nest expressions in Voodoo, so if you have a nested
expression, you will have to break it down to pieces that can be
expressed in Voodoo, and store intermediate results in local variables.
This transformation is called transformation to A normal form.
Also, it is worth noting that the code above calls sum, but discards the
result. Presumably, you want to do something with the result, so you
would probably store that in a local variable, as well; perhaps re-using
tmp:
let tmp add y z
set tmp call sum x tmp
I hope that clears up some things.
Regards,
Bob
--
Give a man a fish and he will eat for a day. Teach a man to fish and he
will eat for a lifetime.
-- Confucius
Robbert Haarman
Thank you for your message.
> What most (all?) common processors provide, but most (all?)
> languages (except assembler) are missing is a means to check
> the carry/overflow flag of the processor. It would be a unique
> feature of Voodoo if Voodoo would provide this.
Indeed. This is a feature I definitely want to have in Voodoo. However,
I am not sure how to design it. Different CPUs support different ways of
reporting overflow. Naturally, I want to design Voodoo's overflow
handling so that it can be implemented for various CPUs without undue
overhead, and so that it doesn't have any overhead at all when it isn't
used.
Regards,
Bob
--
If you want the best seat in the house, you'll have to move the cat.
Ray Dillinger
> What most (all?) common processors provide, but most (all?)
> languages (except assembler) are missing is a means to check
> the carry/overflow flag of the processor. It would be a unique
> feature of Voodoo if Voodoo would provide this.
Indeed. That's the number one reason hardcore math libraries
always have to drop to assembly languages when implementing
extended-precision math.
But the semantics of checking the overflow bit are not consistent
on all hardware platforms. In some architectures (x86) checking
it also clears it, and may involve checking (and clearing) other
error bits as well.
If you're going to abstract it, you have to be very careful about
side effects.
Bear
cr88192
before I had created a language for the purpose of implementing my C
compiler which I call RPNIL...
now, the language is not very good, and the compiler for it is worse, but it
works...
I have just recently began making inroads in the task of getting it ported
to x86-64 (for around the last year, there has been little success on this
front, but I had spent much of the time trying to beat together some sort of
alternative...).
the level of abstraction it operates at is a little higher than the CLI, and
in an abstract sense, the general code structure is actually fairly similar.
like the CLI, it has ended up providing a typesystem, and will likely soon
provide built in support for GC and a Class/Instance object system as
well...
the general syntax is RPN based, and can be compared to that of FORTH or
PostScript.
(I may also end up using the thing as a basis for a JIT engine for JBC and
CIL).
I was stalled out for a long time WRT an x86-64 port by the combination of
the code structure, compiler design, and the SysV calling convention (lets
just say, the SysV convention is not a good match for a stack machine...).
a lazy and half-assed solution here was to drop trying to directly make use
of the SysV calling convention, and instead use my own convention internally
(the SysV convention will then only be used indirectly when trying to use
external code).
the new CC still has some aspects similar to SysV, but borrows far more
heavily from Win64 and cdecl. apart from all the arguments being passed on
the stack, and the use of an elaborate name mangling scheme and other
things, it is mostly the same as Win64.
the idea here is that the linker uses the mangled names as metadata to show
it how to go about linking things together (such as generating stubs to
interface with SysV or Win64, ...). in the varargs case, the mangled name
actually contains all of the arguments being passed to the function in
question (to, rather than simply identifying the callee, it also provides
sufficient info to allow translating the varargs list).
...
one possible feature that does not exist in either the implementation or the
spec is the idea of using "argument packing" for small types (such as small
integers and 32 bit floats), such that a function accepting groups of
integer or float args would take less stack space (the args list would be
packed similar to that of a struct).
however, this would add somewhat to the implementation complexity, and would
be novel (neither Win64 nor SysV do this), and the gain is not likely to
justify the cost. only rarely would this actually save any memory (due to
maintaining stack alignment, ...), and even more rarely would this improve
performance, ...
so, for now I have decided against it...
but oh well, lots of things are possible...
Robbert Haarman
I have been thinking about how one would translate a language like
Scheme to Voodoo. Specifically, I have been thinking about the
combination of closures, continuations, and garbage collection.
As far as closures are concerned, I think closed-over values can be put
in a vector, which is then passed as a function argument when the
closure is invoked. This would mean that a closure consists of a Voodoo
function and a vector.
Scheme's continuations can be invoked zero or more times. This means
that, if there is any chance that a continuation will be created inside
the call chain, but stored outside it, we cannot assume that function
arguments and local variables can be reclaimed when functions exit.
Garbage collection means we need to have need some way to reclaim the
memory used by objects that are no longer used. This requires a way to
determine what parts of memory will not be used. Typically, this is done
by determining which objects are reachable from the current state of the
program, and reclaiming any memory not used by those objects. This
requires a way to determine all reachable objects.
One way to tackle both the potentially indefinite extent of local
variables and the problem of determining all reachable objects is to
allocate call frames on the heap, make sure all the information the
garbage collector needs is in them, and reclaim the frames using the
garbage collector, where frames that may still be used will be reachable
from the currently active frame, so that they won't be reclaimed.
Combining all the above, we get the following:
1. Call frames are allocated on the heap, and contain:
a) Function arguments
b) Local variables
c) A pointer to a vector of closed-over values
d) A pointer to the parent call frame
2. To invoke a closure, one would do the following:
a) Allocate a call frame
b) Fill in local variables
c) Fill in closure pointer (if necessary)
d) Fill in parent pointer (if necessary)
e) Call function with frame as an argument
3. Garbage collection would work as follows: all reachable objects can
be reached from the current call frame. Any memory not in use by
reachable objects can be reclaimed.
4. A continuation needs to store a reference to the innermost call
frame it requires and the address at which to resume execution. Invoking
the continuation then involves restoring the call frame and continuing
execution at the stored address. The reference to the call frame ensures
that it, and its parent frames, will not be collected by the garbage
collector, as long as the continuation remains reachable.
The above would work, and isn't particularly difficult to implement, but
probably isn't as efficient as it could be. Suggestions for improvement
are welcome.
Regards,
Bob
--
The chief cause of problems is solutions.
-- Eric Sevareid
Ray Dillinger
> Hi all,
>
> I have been thinking about how one would translate a language like
> Scheme to Voodoo. Specifically, I have been thinking about the
> combination of closures, continuations, and garbage collection.
>
> As far as closures are concerned, I think closed-over values can be put
> in a vector, which is then passed as a function argument when the
> closure is invoked. This would mean that a closure consists of a Voodoo
> function and a vector.
A problem with this is that you couldn't just copy values; Scheme's
closures can change closed-over values, and the changes have to be
visible in other routines whose lexical scope includes those values,
including other continuations closed over the same values.
So what you have to store in your display vector is pointers to the
closed-over values, which can keep the call frames they're in alive.
Bear
Robbert Haarman
> Robbert Haarman wrote:
>
> > As far as closures are concerned, I think closed-over values can be put
> > in a vector, which is then passed as a function argument when the
> > closure is invoked. This would mean that a closure consists of a Voodoo
> > function and a vector.
>
> A problem with this is that you couldn't just copy values; Scheme's
> closures can change closed-over values, and the changes have to be
> visible in other routines whose lexical scope includes those values,
> including other continuations closed over the same values.
This is true. I didn't want to go into this in my earlier post, to keep
it somewhat simple. There are various possibilities for allowing
programs to close over variables (as distinguished from constants), each
with their own trade-offs.
One way I like is to simply disallow arguments and local variables to be
modified. Then, if you need something modifiable, you would need to
allocate it separately, and the local would store a reference to the
value, rather than the value itself. This is how things work in ML.
The above strategy not ideal for Scheme, because, in Scheme, it may not
be possible to determine which locals are constants and which are
variables. So, to be safe, you would have to assume everything is a
variable, and allocate a data structure for each closed-over value, even
if, in practice, all your variables are actually constants. And in
actual Scheme programs, all or almost all variables usually are actually
constants.
Still, I don't want to go too deeply into this issue now. I am sure
there is plenty of literature on it already, as this very same challenge
crops up when compiling Scheme to other targets than Voodoo. As long as
existing solutions can be implemented in Voodoo, I don't think there is
a problem. If there is a good solution that cannot be implemented in
Voodoo, it may be worth thinking about how Voodoo can be adapted so that
this solution can be implemented.
Thanks for pointing out the issue, though. I'd be interested to hear
what you and others think about it. Without wanting to make Voodoo into
a Scheme-oriented beast, it would be nice if Scheme could be compiled to
efficient code using Voodoo.
Regards,
Bob
--
On the other hand, you have different fingers.
Ray Dillinger
> Thanks for pointing out the issue, though. I'd be interested to hear
> what you and others think about it. Without wanting to make Voodoo into
> a Scheme-oriented beast, it would be nice if Scheme could be compiled to
> efficient code using Voodoo.
As someone who's actually written a scheme compiler, I guess I'm
sensitive to a lot of issues that it involves. I think if you're
going to do a really *good* compilation process for Scheme, you've
got to do a really good whole-program analysis and optimization.
The same is probably true of many other target languages.
Bear
Robbert Haarman
Well, Scheme is a really interesting test case. On the one hand, it's a
small language. On the other hand, it has many features that are
challenging to implement efficiently, especially in high level languages
that don't provide them. Doing better in that regard is definitely a
goal for Voodoo. Which is why I am thinking about how to go about
compiling Scheme to Voodoo. I also have the beginnings of a Scheme to
Voodoo compiler here. Perhaps you would like to help out?
Kind regards,
Bob
--
This sentence is false.
Marco van de Voort
> Robbert Haarman <comp.la...@inglorion.net> writes:
>> - To provide an interface that abstracts away the specific instruction
>> set and calling conventions of target platforms.
>
> languages (except assembler) are missing is a means to check
> the carry/overflow flag of the processor
Which one exactly? Some, like PPC have multiple flag registers.
Mark Wooding
> The above strategy not ideal for Scheme, because, in Scheme, it may
> not be possible to determine which locals are constants and which are
> variables.
Actually you can determine this statically at compile time, and Scheme
compilers do. That is, any SET! form which assigns to a variable must
appear lexically within the form which binds the variable name.
-- [mdw]
James Harris
> Stefan Ram wrote:
> > What most (all?) common processors provide, but most (all?)
> > languages (except assembler) are missing is a means to check
> > the carry/overflow flag of the processor. It would be a unique
> > feature of Voodoo if Voodoo would provide this.
>
> Indeed. That's the number one reason hardcore math libraries
> always have to drop to assembly languages when implementing
> extended-precision math.
>
> But the semantics of checking the overflow bit are not consistent
> on all hardware platforms. In some architectures (x86) checking
> it also clears it, and may involve checking (and clearing) other
> error bits as well.
Are you sure that x86 checking really clears the overflow state? IIRC
there are just two bits in the flags register - Carry and Overflow -
and they should remain set while being tested.
I cannot remember when to check each one.... Is it Carry for unsigned
arithmetic and Overflow for signed?
Then, in the context of Robbert's language what does it do if adding a
signed to an unsigned number? Maybe a short code sequence would be
needed rather than a single instruction.
Or maybe you were talking about the floating point overflow state?
James
James Harris
...
> Keep in
> mind that Voodoo doesn't have any notion of types.
I see you already have a mention on Wikipedia. ;-)
http://en.wikipedia.org/wiki/Voodoo_programming
Seriously, it will be a long time before your language name comes
before links on sorcery in search engines. To avoid confusion why not
change the name to a less-familiar word? Even a change such as Vudoo
or similar would help your cause ... assuming you want search engines
to pick you out, of course.
James
Robbert Haarman
Thanks for pointing that out. I thought about it a bit after I posted
the above, and came to the same conclusion. I guess the only exception
is globals, and these should probably be handled specially in closure
conversion anyway. So things are actually easier than I made them out to
be. :-)
Regards,
Bob
--
Verb another noun.
Robbert Haarman
Thank you for your feedback.
On Sat, Jan 10, 2009 at 12:13:52AM -0800, James Harris wrote:
> On 7 Jan, 05:18, Robbert Haarman <comp.lang.m...@inglorion.net> wrote:
> ...
>
> > Keep in
> > mind that Voodoo doesn't have any notion of types.
>
> I see you already have a mention on Wikipedia. ;-)
>
> http://en.wikipedia.org/wiki/Voodoo_programming
Hahaha, yes. :-)
> Seriously, it will be a long time before your language name comes
> before links on sorcery in search engines. To avoid confusion why not
> change the name to a less-familiar word? Even a change such as Vudoo
> or similar would help your cause ... assuming you want search engines
> to pick you out, of course.
Actually, I am really happy with the name, and also with the proximity
between "Voodoo programming" and "Voodoo programming language". The
references to Vodou (the religion, if that's the right word to use) and
Voodoo programming are, of course, fully intended.
As far as search engines are concerned, Voodoo (the programming
language) is among the top hits for "voodoo programming language" on
Google and Lycos, and the top hit on Altavista and Yahoo!. Live Search
results aren't as good, but then, that's not unusual. Overall, I am very
satisfied with the results.
Regards,
Bob
--
You are in a maze of twisted little characters, all different.
-- Me, learning Chinese
nightmie
wrote:
> Indeed. This is a feature I definitely want to have in Voodoo. However,
> I am not sure how to design it. Different CPUs support different ways of
> reporting overflow. Naturally, I want to design Voodoo's overflow
> handling so that it can be implemented for various CPUs without undue
> overhead, and so that it doesn't have any overhead at all when it isn't
> used.
Should be noted that careless play with flags can really hurt
optimization.
Consider design where flag is returned by built-in inline function:
if( c + d ){....}
a = b + c
d = c + d
if( carry_flag() ){.....}
if after common subexpression elimination compiler generates
t1 = c + d
if t1 then {...}
a = b + c
d = t1
if carry_flag() ...
everything will die painfully because now carry_flag() does not check
what it intended to check.
So imho using global function or global variable looks like bad idea.
Global var/fun hurt not only CSE, but also dead-code elimination:
int foo(a, b : int){
int d = a + b
if carry_flag() then f()
}
if DCE carelessly removes d variable
int foo(a, b : int){
if carry_flag() then f()
}
then everything will die again.
Maybe some sort of tuples can be handy there:
if( c + d ){....}
a = b + c
(d, cf1) = c + d
if( cf1 ){.....}
and
int foo(a, b : int){
(_, cf) = a + b
if cf then f()
}
do not increase complexity of optimizer comparing to global var/fun.
nightmie
>
> A hypothetical higher-level language might be specified so that
>
> try
> { a = x * y + x;
> b =( a + c )* z; }
> catch( final java.lang.Overflow overflow )
> { java.lang.System.err.println( "overflow" ); }
>
> will print »overflow« if an overflow happened during the evaluation
> of any of the expressions with »*« or »+« above.
This again imho will have very negative effect on optimization.
Because now instead of generating
; this is pseudo asm
MUL R_a, R_x, R_Y ; a = x * y
ADD R_a, R_a, R_z ; a += z
ADD R_b, R_a, R_c ; b = a + c
MUL R_b, R_b, R_z ; b *= z
which is nice and neat
compiler will generate something like
MUL R_a, R_x, R_Y ; a = x * y
BRANCH_IF_OVERFLOW .L1
ADD R_a, R_a, R_z ; a += z
BRANCH_IF_OVERFLOW .L1
ADD R_b, R_a, R_c ; b = a + c
BRANCH_IF_OVERFLOW .L1
MUL R_b, R_b, R_z ; b *= z
BRANCH_IF_OVERFLOW .L1
Branches afaik are not good for executing several operations per
clock.
Beside, some of these conditional branches may be not necessary. And
compiler may not be able to prove it and remove.
If such paranoid check is needed, one can implement it as class in
library, that checks CF after every operation. For example boost has
some cast function(numeric_cast?) that raises exception if destination
operand can not fit source.
My point is that it's pointless to implement access to carry-flag if
optimizer will be ruined by such access.
Marco van de Voort
> people would like to know at runtime whether the value of the
> expression »x*y« is equal to x·y (the common product of two
> natural numbers).
>
> Checking this is not easy, and even if a programmer figures
> out how to do it, it still will be slow. Usually, the required
> information already will be in one of those multiple flag
> registers of the processor.
You are missing the point. My point is that a lot of processors have
multiple of such sets of flags (Z,C,O etc). This allows you to do stuff like
(in pseudo code manor)
cmp cr2,a,b // assign the flag results of this comparison to control
(flag) register cr2.
<do other stuff here that uses the default flag register>
je cr2:somelabel // test cr2 for Zero and branch
IOW you only model one set of such bits, while there might be several (PPC
has 3 or 4)
Robbert Haarman
> Some thoughts about design.
> Should be noted that careless play with flags can really hurt
> optimization.
> Consider design where flag is returned by built-in inline function:
>
> if( c + d ){....}
> a = b + c
> d = c + d
> if( carry_flag() ){.....}
>
> if after common subexpression elimination compiler generates
>
> t1 = c + d
> if t1 then {...}
> a = b + c
> d = t1
> if carry_flag() ...
>
> everything will die painfully because now carry_flag() does not check
> what it intended to check.
>
> So imho using global function or global variable looks like bad idea.
> Global var/fun hurt not only CSE, but also dead-code elimination:
Yes, exactly. Flags are side effects, and side effects make program
analysis (and thus optimization) more difficult. If one wants to do
something with the flags at all, I would much rather follow Marco's
example and have the flags explicitly mentioned in the code.
Thank you for your insightful comments.
Bob
--
"The nice thing about standards is that you have so many to choose from."
-- Andrew S. Tanenbaum