8 ms·

Deca - a systems language based on modern PL principles

119 points by nponeccop 15y ago

andrewcooke 15y ago
how do you combine first class functions (and so closures) with no garbage collection? don't you end up with possibly multiple references to memory and no way of knowing who owns it?
- nponeccop 15y ago
  If you read the dissertation, it turns out that variables are captured by value. But even if they are captured by reference - solutions are possible such as the one in C++11. The decac doesn't provide more memory safety than C, so there are no problems :) Yet another solution is to inline all higher-order functions so no closures exist at runtime.
  - eli_gottlieb 15y ago
    Actually, this issue is what spurred a major evolution in the language. I hadn't had a real region or effect system before, and now I do. Why? I needed some way to register what pointers (regions) are getting captured by an existential package (aka: a lexical closure). Since regions are now registered as part of an existential package, the regions captured by a package can be constrained to suit the region of the stack up to which a package is being returned. In short, closures now remember what pointers they capture, and you won't be allowed to return a closure over a pointer further up the stack than safe. Other than that, closures capture by value, copying the captured variable into an environment structure.
- gsg 15y ago
  If you have a function that returns a function, basically you need to rewrite things to lift the referenced state into the outer scope. In pseudo-C: (void -> int) incrementer(int initial_value) { int count = initial_value; return lambda() { return count++; } } might be rewritten as: struct hidden_environment_type { int count; } int incrementer_lambda(hidden_environment_type *env) { return env->count++; } void incrementer(hidden_environment_type *hidden_arg, int initial_value) { hidden_arg->count = initial_value; } Now the caller will allocate a variable of type hidden_environment_type, and pass its address as the first (artificial) argument. Note that lambda functions require a different calling convention to C function pointers, since they need to be passed a pointer to their environment in addition to their regular arguments. Introducing lambdas either requires some resolution of this complication, such as specialisation machinery (ie in C++11, templates provide the necessary specialisation). Another option is to use the environment-passing convention for every indirect call, possibly giving a minor performance hit for calling raw function pointers. Another issue is that the size of an environment type depends on the code of a function involving it, so lambdas don't have uniform size unless some additional indirection is introduced, probably to heap storage (Apple's blocks extension to C takes this approach). This makes it either impossible or slightly more expensive to store lambda functions in data structures, depending on which implementation you choose. After all this, your ownership/lifetime question boils down to "who is holding onto the instance of hidden_environment_type?", which is a pretty simple question to answer in C-like languages.
mvzink 15y ago
Looks awesome, especially the type system. Check out http://code.google.com/p/decac/source/browse/examples/list.dca http://code.google.com/p/decac/source/browse/examples/list.d... I'd love to see some discussions on possible/practical shortcomings.
- nponeccop 15y ago
  The type system looks novel, but it doesn't provide controlled effects or safety as the system for Disciple language described in the "Type inference and optimization in impure world" paper. So it doesn't qualify as 'awesome' IMO
  - eli_gottlieb 15y ago
    The docs are out of date. I read the Disciple papers about a month after finishing the thesis, and immediately began working out how to add "back" (regions were always intended) regions and effects.
    - nponeccop 15y ago
      Yeah, I have the same story. I have long wanted a "mutable" type system for my HNC project ( https://github.com/kayuri/HNC/wiki https://github.com/kayuri/HNC/wiki, http://code.google.com/p/inv/ http://code.google.com/p/inv/ ) - it was here on HackerNews about 1 year ago but got little to no interest. I asked on cstheory.stackexchange.com but got no useful answers. And then someone pointed my attention to DDC. I knew about it but I thought it was just an eager revamping of Haskell, just like many other eager haskells (speculative execution etc) out there.
- eli_gottlieb 15y ago
  The "newsig" branch is current development. That old stuff still has older syntax and semantics.
pwpwp 15y ago
Looks interesting. When I read "modern PL principles" I was afraid to read about auto-generated getters and setters or something. :P
- nponeccop 15y ago
  Looks like you have never took academia papers seriously :)
olliesaunders 15y ago
Isn’t the name of the language Decac?
- nponeccop 15y ago
  The dissertation says it's Deca. DecaC stands for Deca Compiler.
agumonkey 15y ago
Finally a successor to the now frozen bitc
- nponeccop 15y ago
  What about Cyclone?
  - agumonkey 15y ago
    I'm not sure I've even heard the name once. Looks interesting , gradually safer than C, I like that.
    - nponeccop 15y ago
      Well, BitC is not too popular either. Another interesting experiment is Sing#/Singularity, which is a successful attempt to get IO performance of FreeBSD despite designing whole OS in modified dependently-typed C# with usual JIT and garbage collection. The question whether GC is applicable in memory-constrained environments is still open - I couldn't find a single research in this direction.
- deleted 15y ago
  [deleted]
tom626 15y ago
They should have used more C-like syntax.
- skucherenko 15y ago
  http://bikeshed.com/ http://bikeshed.com/
eternalban 15y ago
I greped for "core", "memory manager", "thread", "threading", and "cache", in the pdf [1]. Am I missing something? I'll probably get flak for this, but this programmer looks for a modern systems language that directly addresses these concerns. "The fundamental problems of a systems-programming task or environment are hard limits on computational resources and a lack of safety protections. Systems programs have to deal with hardware-imposed limitations on their CPU time, registers, memory space, storage space on I/O devices, and I/O bandwidth. They also often have to deal with a lack of the safety features normally given to most programming environments: garbage-collection of memory, validation of memory accesses, synchronization primitives, abstracted access to I/O devices, and transparent multitasking. In fact, the point of systems programming is usually to create such abstractions and program such protections." Let's take Go, as an example. (Or D). Per above definition, neither is a "systems programming" language. I know for a fact [2] that Go team would disagree. So what is the accepted definition of a "modern" systems programming language? [1]: http://code.google.com/p/decac/downloads/detail?name=Deca%20Thesis.pdf&can=2&q= http://code.google.com/p/decac/downloads/detail?name=Deca%20... [2]: http://golang.org/doc/go_faq.html#What_is_the_purpose_of_the_project http://golang.org/doc/go_faq.html#What_is_the_purpose_of_the...
- wbhart 15y ago
  One of the examples in the repository is an implementation of malloc. I tend to think of Go as an attempt to redefine what a systems programming language is (hence the "modern"). I don't think that there can be an established definition of what a modern systems language is, otherwise it would no longer be termed modern. Almost by definition theorists will differ on what the essential characteristics must be.
  - eternalban 15y ago
    > One of the examples in the repository is an implementation of malloc. Right. And (imho) malloc is quite possibly an "old fashioned" way of looking at things: function malloc(num_bytes: nat): @byte A reference to a byte block obtained from specifying the number of bytes! I would like to see the modern memory manger be type aware, have a very rich memory model, and allow for the propagation of application level semantics to OS (so they can cooperate in dealing with the current issue: memory access latencies and concurrency). > I don't think that there can be an established definition of [a] modern systems language Key word is "modern" so here is an attempt to box that a bit: There are 2 possible dimensions to the notion of modern: 1 - it addresses new hardware realities 2 - it enables "progress" in dealing with matter rendered difficult by existing paradigms of system programming. The realities of a modern system surely include: multi-core SMP; strong likelihood to be employed as distributed nodes; virtualization. So "modern" platforms and deployment patterns are not addressed. Second, Deca, I gather, would delegate dealing with all this to some higher level (user level) framework built on top of the language. I don't see any progress in that critical front, either.
wbhart 15y ago
It's great to see a language which doesn't ignore 20th and 21st century programming language theory. It's tremendously boring waiting for the future to happen.... Anyhow, the type system looks quite interesting. The choice of LLVM for C interface and performance is also really sensible. I was surprised to find the language implemented in Scala and Java though. Perhaps there will be some kind of bootstrap, or maybe the ability to access the java libraries is intentional. Without proper documentation it is a bit hard to evaluate this more fully at this stage. I looked but didn't find many docs yet. Certainly a language to watch.
- eli_gottlieb 15y ago
  The language is a compiled language, with the JVM being used (originally) because I wanted a particular parser generator. Deca code can't access Java libraries because Deca code compiles to LLVM bitcode and thence to machine code. decac is a compiler, not an interpreter, so it takes the Deca code in and outputs the LLVM bitcode. Sorry about the lack of docs. I've been slowly dumping my undergraduate thesis on this into the wiki, but the language has been evolving and I've been starting a career. Oy ;-).
  - _Y_ 15y ago
    Sorry to nag, but how is outputting to LLVM bitcode not interpreting? You are taking source code and turning it into intermediate form (i.e. LLVM bitcode), no?
    - skrebbel 15y ago
      An interpreter means a program that runs a program, straight from its source code. A compiler transforms a program from one format into another. decac does not execute programs, so it's not an interpreter.
    - nponeccop 15y ago
      LLVM bytecode does not exist after linking - it turns into usual machine code. It is not even a JIT compiler, talk less of an interpreter.
Dn_Ab 15y ago
I keep a (small) list of active awesome and interesting alternatives to C. Cyclone has been mentioned already, adding Deca now. the other two I know are: * ATS http://www.ats-lang.org/#what_is_ats_good_for http://www.ats-lang.org/#what_is_ats_good_for * Clay http://claylabs.com/clay/ http://claylabs.com/clay/
- nickik 15y ago
  Dont you know about Rust? If you do why is it not on the list?
  - rntz 15y ago
    Rust, while interesting and admirable, isn't quite as low-level as C or Deca. For example, one of Deca's explicit goals is to not require a garbage collector or a runtime library. Rust has GC and a light-weight-threading runtime. So it's not quite a replacement for C, though it's certainly a good replacement for much of the application-level programming C and C++ are (unfortunately) widely used for.
    - nickik 15y ago
      Ok, thx. Rust certently has a runtime, cant argue with that. I thought Rust allows a pretty tight control over allocation with the pointer hierarchy feature. The GC is designed not to be global and should be pretty easy ignore. They even have diffrent kinds lambdas to allow the programmer if the should be allocated on the heap or the stack. I have not done alot of low level programmig but I want to learn more about writting Jits and the pretty much need to be rather low level atm there is not really an alternative then writting them in C (witch sucks).
  - Dn_Ab 15y ago
    Yes I know of Rust and think it's very interesting. For most system level programming it should be an excellent choice. It's great that the dearth of systems capable languages is something that is becoming less of an issue. But when i was making the list I was thinking about if the language could possibly be used in an embed context. C is still king there. Rust I believe, is partially garbage collected in a way that is not practically avoidable. Any use of boxed types or abstract datatypes will incur this penalty. So with that criterion rust is not an option, in an embed system continuous execution is most vital. The languages I listed are either not garbage collected or with an ability to turn it off or use an alternative to abstract datatypes and have basically no overhead. The last time I saw Rust mentioned on HN a team member validly stated that such concerns are not the priority at the moment.
elehack 15y ago
Nice to see something actually trying a CLOS-style object system. There are good ideas in there that don't get enough presence in more recent language efforts.
- nickik 15y ago
  Look at Dylan, stuff started happening again. http://opendylan.org/ http://opendylan.org/
- nponeccop 15y ago
  I wonder what happened to SELF-like object systems (slots, prototypes and all that).
  - fanf2 15y ago
    JavaScript
    - nponeccop 15y ago
      I mean high-performance implementations. Techniques to (statically) compile prototypes into efficient code were developed, but they are largely irrelevant to Javascript. High-performance modern implementations of JS rely on tracing JIT.
      - cyrus_ 15y ago
        Pretty sure polymorphic inline caches are standard fare in both Javascript and other VMs (JVM, CLR, etc.). What other techniques are you referring to?
zem 15y ago
ltu discussion: lambda-the-ultimate.org/deca
andrewflnr 15y ago
I see that "lispy macros" will not be supported, but one of the things that bugs me about C (in my brief experience) is the verbosity and repititiousness. Good generics will help, but I'd still like to see a better macro system than the C preprocessor. One possible feature that stands out would be macros local to a scope. I actually did this, defined a macro right in the middle of a function to automate some error-handling junk. It felt nasty, but not quite as nasty as copy-pasting or retyping the code, as long as I don't try to re-use the name. It would be nice if my language handled stuff like this. This is obviously not a huge issue. The language looks awesome.
- obtu 15y ago
  Macros can be band-aid to overly verbose languages, but plenty of languages are concise without (whereas C is particularly bad). Higher order functions and an expressive type system (features it shares with OCaml, Oz, etc) are where the magic is.

119 points by nponeccop 15y ago

how do you combine first class functions (and so closures) with no garbage collection? don't you end up with possibly multiple references to memory and no way of knowing who owns it?

nponeccop 15y ago
If you read the dissertation, it turns out that variables are captured by value. But even if they are captured by reference - solutions are possible such as the one in C++11. The decac doesn't provide more memory safety than C, so there are no problems :) Yet another solution is to inline all higher-order functions so no closures exist at runtime.
- eli_gottlieb 15y ago
  Actually, this issue is what spurred a major evolution in the language. I hadn't had a real region or effect system before, and now I do. Why? I needed some way to register what pointers (regions) are getting captured by an existential package (aka: a lexical closure). Since regions are now registered as part of an existential package, the regions captured by a package can be constrained to suit the region of the stack up to which a package is being returned. In short, closures now remember what pointers they capture, and you won't be allowed to return a closure over a pointer further up the stack than safe. Other than that, closures capture by value, copying the captured variable into an environment structure.
gsg 15y ago
If you have a function that returns a function, basically you need to rewrite things to lift the referenced state into the outer scope. In pseudo-C: (void -> int) incrementer(int initial_value) { int count = initial_value; return lambda() { return count++; } } might be rewritten as: struct hidden_environment_type { int count; } int incrementer_lambda(hidden_environment_type *env) { return env->count++; } void incrementer(hidden_environment_type *hidden_arg, int initial_value) { hidden_arg->count = initial_value; } Now the caller will allocate a variable of type hidden_environment_type, and pass its address as the first (artificial) argument. Note that lambda functions require a different calling convention to C function pointers, since they need to be passed a pointer to their environment in addition to their regular arguments. Introducing lambdas either requires some resolution of this complication, such as specialisation machinery (ie in C++11, templates provide the necessary specialisation). Another option is to use the environment-passing convention for every indirect call, possibly giving a minor performance hit for calling raw function pointers. Another issue is that the size of an environment type depends on the code of a function involving it, so lambdas don't have uniform size unless some additional indirection is introduced, probably to heap storage (Apple's blocks extension to C takes this approach). This makes it either impossible or slightly more expensive to store lambda functions in data structures, depending on which implementation you choose. After all this, your ownership/lifetime question boils down to "who is holding onto the instance of hidden_environment_type?", which is a pretty simple question to answer in C-like languages.

mvzink 15y ago

Looks awesome, especially the type system. Check out http://code.google.com/p/decac/source/browse/examples/list.dca http://code.google.com/p/decac/source/browse/examples/list.d... I'd love to see some discussions on possible/practical shortcomings.

nponeccop 15y ago
The type system looks novel, but it doesn't provide controlled effects or safety as the system for Disciple language described in the "Type inference and optimization in impure world" paper. So it doesn't qualify as 'awesome' IMO
- eli_gottlieb 15y ago
  The docs are out of date. I read the Disciple papers about a month after finishing the thesis, and immediately began working out how to add "back" (regions were always intended) regions and effects.
  - nponeccop 15y ago
    Yeah, I have the same story. I have long wanted a "mutable" type system for my HNC project ( https://github.com/kayuri/HNC/wiki https://github.com/kayuri/HNC/wiki, http://code.google.com/p/inv/ http://code.google.com/p/inv/ ) - it was here on HackerNews about 1 year ago but got little to no interest. I asked on cstheory.stackexchange.com but got no useful answers. And then someone pointed my attention to DDC. I knew about it but I thought it was just an eager revamping of Haskell, just like many other eager haskells (speculative execution etc) out there.
eli_gottlieb 15y ago
The "newsig" branch is current development. That old stuff still has older syntax and semantics.

pwpwp 15y ago

Looks interesting. When I read "modern PL principles" I was afraid to read about auto-generated getters and setters or something. :P

nponeccop 15y ago
Looks like you have never took academia papers seriously :)

olliesaunders 15y ago

Isn’t the name of the language Decac?

nponeccop 15y ago
The dissertation says it's Deca. DecaC stands for Deca Compiler.

agumonkey 15y ago

Finally a successor to the now frozen bitc

nponeccop 15y ago
What about Cyclone?
- agumonkey 15y ago
  I'm not sure I've even heard the name once. Looks interesting , gradually safer than C, I like that.
  - nponeccop 15y ago
    Well, BitC is not too popular either. Another interesting experiment is Sing#/Singularity, which is a successful attempt to get IO performance of FreeBSD despite designing whole OS in modified dependently-typed C# with usual JIT and garbage collection. The question whether GC is applicable in memory-constrained environments is still open - I couldn't find a single research in this direction.
deleted 15y ago
[deleted]

tom626 15y ago

They should have used more C-like syntax.

skucherenko 15y ago
http://bikeshed.com/ http://bikeshed.com/

eternalban 15y ago

I greped for "core", "memory manager", "thread", "threading", and "cache", in the pdf [1]. Am I missing something? I'll probably get flak for this, but this programmer looks for a modern systems language that directly addresses these concerns. "The fundamental problems of a systems-programming task or environment are hard limits on computational resources and a lack of safety protections. Systems programs have to deal with hardware-imposed limitations on their CPU time, registers, memory space, storage space on I/O devices, and I/O bandwidth. They also often have to deal with a lack of the safety features normally given to most programming environments: garbage-collection of memory, validation of memory accesses, synchronization primitives, abstracted access to I/O devices, and transparent multitasking. In fact, the point of systems programming is usually to create such abstractions and program such protections." Let's take Go, as an example. (Or D). Per above definition, neither is a "systems programming" language. I know for a fact [2] that Go team would disagree. So what is the accepted definition of a "modern" systems programming language? [1]: http://code.google.com/p/decac/downloads/detail?name=Deca%20Thesis.pdf&can=2&q= http://code.google.com/p/decac/downloads/detail?name=Deca%20... [2]: http://golang.org/doc/go_faq.html#What_is_the_purpose_of_the_project http://golang.org/doc/go_faq.html#What_is_the_purpose_of_the...

wbhart 15y ago
One of the examples in the repository is an implementation of malloc. I tend to think of Go as an attempt to redefine what a systems programming language is (hence the "modern"). I don't think that there can be an established definition of what a modern systems language is, otherwise it would no longer be termed modern. Almost by definition theorists will differ on what the essential characteristics must be.
- eternalban 15y ago
  > One of the examples in the repository is an implementation of malloc. Right. And (imho) malloc is quite possibly an "old fashioned" way of looking at things: function malloc(num_bytes: nat): @byte A reference to a byte block obtained from specifying the number of bytes! I would like to see the modern memory manger be type aware, have a very rich memory model, and allow for the propagation of application level semantics to OS (so they can cooperate in dealing with the current issue: memory access latencies and concurrency). > I don't think that there can be an established definition of [a] modern systems language Key word is "modern" so here is an attempt to box that a bit: There are 2 possible dimensions to the notion of modern: 1 - it addresses new hardware realities 2 - it enables "progress" in dealing with matter rendered difficult by existing paradigms of system programming. The realities of a modern system surely include: multi-core SMP; strong likelihood to be employed as distributed nodes; virtualization. So "modern" platforms and deployment patterns are not addressed. Second, Deca, I gather, would delegate dealing with all this to some higher level (user level) framework built on top of the language. I don't see any progress in that critical front, either.

wbhart 15y ago

It's great to see a language which doesn't ignore 20th and 21st century programming language theory. It's tremendously boring waiting for the future to happen.... Anyhow, the type system looks quite interesting. The choice of LLVM for C interface and performance is also really sensible. I was surprised to find the language implemented in Scala and Java though. Perhaps there will be some kind of bootstrap, or maybe the ability to access the java libraries is intentional. Without proper documentation it is a bit hard to evaluate this more fully at this stage. I looked but didn't find many docs yet. Certainly a language to watch.

eli_gottlieb 15y ago
The language is a compiled language, with the JVM being used (originally) because I wanted a particular parser generator. Deca code can't access Java libraries because Deca code compiles to LLVM bitcode and thence to machine code. decac is a compiler, not an interpreter, so it takes the Deca code in and outputs the LLVM bitcode. Sorry about the lack of docs. I've been slowly dumping my undergraduate thesis on this into the wiki, but the language has been evolving and I've been starting a career. Oy ;-).
- _Y_ 15y ago
  Sorry to nag, but how is outputting to LLVM bitcode not interpreting? You are taking source code and turning it into intermediate form (i.e. LLVM bitcode), no?
  - skrebbel 15y ago
    An interpreter means a program that runs a program, straight from its source code. A compiler transforms a program from one format into another. decac does not execute programs, so it's not an interpreter.
  - nponeccop 15y ago
    LLVM bytecode does not exist after linking - it turns into usual machine code. It is not even a JIT compiler, talk less of an interpreter.

Dn_Ab 15y ago

I keep a (small) list of active awesome and interesting alternatives to C. Cyclone has been mentioned already, adding Deca now. the other two I know are: * ATS http://www.ats-lang.org/#what_is_ats_good_for http://www.ats-lang.org/#what_is_ats_good_for * Clay http://claylabs.com/clay/ http://claylabs.com/clay/

nickik 15y ago
Dont you know about Rust? If you do why is it not on the list?
- rntz 15y ago
  Rust, while interesting and admirable, isn't quite as low-level as C or Deca. For example, one of Deca's explicit goals is to not require a garbage collector or a runtime library. Rust has GC and a light-weight-threading runtime. So it's not quite a replacement for C, though it's certainly a good replacement for much of the application-level programming C and C++ are (unfortunately) widely used for.
  - nickik 15y ago
    Ok, thx. Rust certently has a runtime, cant argue with that. I thought Rust allows a pretty tight control over allocation with the pointer hierarchy feature. The GC is designed not to be global and should be pretty easy ignore. They even have diffrent kinds lambdas to allow the programmer if the should be allocated on the heap or the stack. I have not done alot of low level programmig but I want to learn more about writting Jits and the pretty much need to be rather low level atm there is not really an alternative then writting them in C (witch sucks).
- Dn_Ab 15y ago
  Yes I know of Rust and think it's very interesting. For most system level programming it should be an excellent choice. It's great that the dearth of systems capable languages is something that is becoming less of an issue. But when i was making the list I was thinking about if the language could possibly be used in an embed context. C is still king there. Rust I believe, is partially garbage collected in a way that is not practically avoidable. Any use of boxed types or abstract datatypes will incur this penalty. So with that criterion rust is not an option, in an embed system continuous execution is most vital. The languages I listed are either not garbage collected or with an ability to turn it off or use an alternative to abstract datatypes and have basically no overhead. The last time I saw Rust mentioned on HN a team member validly stated that such concerns are not the priority at the moment.

elehack 15y ago

Nice to see something actually trying a CLOS-style object system. There are good ideas in there that don't get enough presence in more recent language efforts.

nickik 15y ago
Look at Dylan, stuff started happening again. http://opendylan.org/ http://opendylan.org/
nponeccop 15y ago
I wonder what happened to SELF-like object systems (slots, prototypes and all that).
- fanf2 15y ago
  JavaScript
  - nponeccop 15y ago
    I mean high-performance implementations. Techniques to (statically) compile prototypes into efficient code were developed, but they are largely irrelevant to Javascript. High-performance modern implementations of JS rely on tracing JIT.
    - cyrus_ 15y ago
      Pretty sure polymorphic inline caches are standard fare in both Javascript and other VMs (JVM, CLR, etc.). What other techniques are you referring to?

zem 15y ago

ltu discussion: lambda-the-ultimate.org/deca

andrewflnr 15y ago

I see that "lispy macros" will not be supported, but one of the things that bugs me about C (in my brief experience) is the verbosity and repititiousness. Good generics will help, but I'd still like to see a better macro system than the C preprocessor. One possible feature that stands out would be macros local to a scope. I actually did this, defined a macro right in the middle of a function to automate some error-handling junk. It felt nasty, but not quite as nasty as copy-pasting or retyping the code, as long as I don't try to re-use the name. It would be nice if my language handled stuff like this. This is obviously not a huge issue. The language looks awesome.

obtu 15y ago
Macros can be band-aid to overly verbose languages, but plenty of languages are concise without (whereas C is particularly bad). Higher order functions and an expressive type system (features it shares with OCaml, Oz, etc) are where the magic is.