tag:blogger.com,1999:blog-28132570584409830722024-03-05T21:34:23.740-08:00Machine WordsOccasional thoughts on sofware architecure and programming languagesTalinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.comBlogger120125tag:blogger.com,1999:blog-2813257058440983072.post-13583651901662004582021-09-01T21:30:00.002-07:002021-09-01T21:30:49.385-07:00Test Post<p> It's been 10 years since I posted anything here (basically since I left the blogger.com team at Google).</p><p>Curious to see how well this still works. And...it still sucks for posting source code examples. Oh well.</p>Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-2760329916764410122012-07-24T14:51:00.000-07:002012-07-24T14:51:02.432-07:00Scripting Languages for Games - the good, the bad, and the appallingHaving worked on a lot of games, I've also encountered and worked with a lot of scripting languages embedded within games. Here's a list of a few of the ones that I have worked with:<br />
<br />
<ul>
<li>SAGA and SAGA 2 (Scripts for Animated Graphic Adventures), my own language which I created for <a href="http://wyrmkeep.com/ite/">Inherit the Earth</a> and<a href="http://www.youtube.com/watch?v=o5FZxUVLMjs"> Faery Tale Adventure 2</a>.</li>
<li><a href="http://www.lua.org/">Lua</a>, a lightweight general purpose language for embedding, used in many games including World of Warcraft</li>
<li>Edith, the scripting language used for The Sims and The Sims 2.</li>
<li>Swarm, a particle system language developed by Andrew Willmott at Electronic Arts, used in Sim City 4, Sims 2, Spore, and many other EA games.</li>
<li>Edibles, a scripting language created by PostLinear Entertainment (1998).</li>
<li>UnrealScript, the scripting language for the Unreal game engine.</li>
</ul>
<div>
Some of these languages were a pleasure to work with - tight, well designed languages that provided clear benefits to the game development process. Lua and Swarm are both shining examples of this.</div>
<div>
<br /></div>
<div>
On the other hand, some of these languages were not so wonderful - poorly designed and cumbersome to work with.</div>
<div>
<br /></div>
<div>
And then there is a third category - cases where the game developers shouldn't have used a scripting language at all. The Sim City 4 city advisor system comes to mind - there was no reason to use a general purpose scripting language for this, the advisor messages could have been stored as text string resources with far less complexity.</div>
<div>
<br /></div>
<h3>
Imperative Scripting Languages</h3>
<div>
<br /></div>
<div>
Another observation is that most of these languages aren't terribly innovative as languages. With the exception of Swarm, all of the above languages are fairly standard imperative programming languages, not much different from BASIC, Pascal or JavaScript.</div>
<div>
<br /></div>
<div>
Take Edith for example. Edith's main innovation was that it was a "graphical" programming language, where game content designers could place functional blocks on the page and wire them together. Semantically, however, these diagrams were nothing more than flowcharts - one of the <i>least</i> expressive forms of programming known to computer science. As one developer put it "Edith is basically Assembly language with the user interface of LEGO Mindstorms".</div>
<div>
<br /></div>
<div>
UnrealScript had a built-in "state machine" control flow construct - but the same thing could have been done using a conventional switch statement with almost the same number of lines of code.</div>
<div>
<br /></div>
<div>
Lua, which is the most general purpose language on the list, also has the largest number of innovative language features - for example, Lua supports continuations, which is a powerful way to deal with asynchronous processes. But for the most part, there's not much difference between what you can do in Lua and what you can do in Python.</div>
<div>
<br /></div>
<div>
In general, there is very little that can be expressed in these languages that cannot be expressed in C++ or Java or Python just as easily. Which leads to the obvious question - what's the benefit of using these languages instead of coding the game logic in C++? Why go through all the trouble of embedding a language in the first place?</div>
<div>
<br /></div>
<div>
The answer lies not in the language syntax, but rather in it's compilation and runtime environment. These embedded languages all have three major advantages over C++:</div>
<div>
<ul>
<li>Compilation is very fast.</li>
<li>Individual modules can be recompiled without recompiling and re-linking all other modules.</li>
<li>Recompiled modules can be dynamically loaded into a running version of the game without having to restart it.</li>
</ul>
</div>
<div>
This means that the iterative development cycle is extremely fast. Instead of waiting 5 minutes for the program to compile and link - which is the experience of the typical C++ developer - the programmer using these script languages can have the new behavior manifest within the game within seconds after they hit "save" in their editor.</div>
<div>
<br /></div>
<div>
Another benefit is that the complexity of these languages is often much lower than the language that the game engine is written in, so that game companies can hire less skilled (and less expensive) staff to create the game content with a minimum of training. This means that the programming staff for a game tends to be divided into two separate "castes" - software engineers and "scripters".</div>
<div>
<br /></div>
<div>
Although one might be tempted to think of scripters as being on a somewhat lower level than the software engineers, in many cases the job of a scripter was just as challenging and demanding as any. For example, one of my experiences working on Faery Tale 2 was that scripters would discover bugs in the underlying game engine, and being impatient with the slow pace of bug fixes, would write scripts that were essentially workarounds for those bugs.</div>
<div>
<br /></div>
<h3>
Non-imperative languages: Swarm</h3>
<div>
<span style="background-color: white;"><br /></span></div>
Now I want to talk a bit about Swarm, because it is so different from all the others. Swarm is not an imperative language - there is no flow of control, no "if" statements or conditional branches, no "for" loops or iteration statements, and so on. However, even without these language constructs, it can be used to specify complex behavior.<div>
<br /><div>
Swarm is a declarative language for describing particle system. Particles are visual effects like sparks, smoke, water droplets, bullets, clouds, dust, and other entities that typically appear in large swarms with short lifetimes. A particle <i>system</i> consists of an emitter - an object that generates particles - and a particle specification, that is a description of the type of particles that the emitter generates.</div>
<div>
<br /></div>
<div>
An emitter will typically have properties such as emission rate (how fast particles are generated), a delay time before the first particle is emitted, a duration, and a specification for the initial trajectory of the particles. For example, you can have omnidirectional emitters that emit particles in all directions, cone-shaped emitters, square emitters, and so on.</div>
<div>
<br /></div>
<div>
Particles generated by a given emitter have a set of properties, such as:</div>
<div>
<br /></div>
<div>
<ul>
<li><span style="background-color: white;">color</span></li>
<li><span style="background-color: white;">transparency</span></li>
<li><span style="background-color: white;">size</span></li>
<li><span style="background-color: white;">velocity</span></li>
<li><span style="background-color: white;">duration (how long the particle lasts)</span></li>
<li><span style="background-color: white;">whether the particle as affected by gravity, wind, or other forces</span></li>
<li><span style="background-color: white;">whether the particle can collide with terrain, buildings, characters, or other particles</span></li>
<li><span style="background-color: white;">whether the particle is displayed using a 2D image or a 3D model</span></li>
<li><span style="background-color: white;">whether the particle's orientation is aligned with it's trajectory or with the player's view</span></li>
</ul>
<div>
...and so on. Virtually all of these properties can be specified as functions of time - such as a particle that starts out opaque and slowly becomes transparent. And virtually all of these properties can have a random component added to them as well.</div>
</div>
<div>
<br /></div>
<div>
In addition, particles have conditions which can trigger actions when a particular event occurs. For example, a particle representing a bomb or grenade could have a trigger condition when the particle collides with a surface or with the ground. The triggered action could be to create a new particle emitter representing the resulting explosion.</div>
<div>
<br /></div>
<div>
All of the emitters, particles, and trigger actions can be specified within the Swarm source files. Complex behaviors are specified by setting up chains of effects - a particle of type A might create an emitter of type B when a certain condition is reached, and the particles emitted by B might create a new particles of type C, and so on.</div>
<div>
<br /></div>
<div>
For example, one artist on Sim City 4 (Ocean Quigley) created a complex alien invasion script with a giant robot descending from the skies on a blast of rocket jets who then attacked the city with flying discs of destruction, and then blasted back off into space - and all of this was done with a single Swarm script, with no changes to the game engine!</div>
<div>
<br /></div>
<div>
Another impressive demo (which, alas, did not make it into the shipped game) consisted of a water erosion simulation. Andrew had added a new particle effect type which would cause a small depression in the terrain whenever it was struct by that particle. He could then create emitters which represented water sources emitting droplets of water, which would then flow downhill, eroding gullies and channels in the terrain.</div>
<div>
<br /></div>
<div>
If you think about particles as processes, then Swarm is a language of implicit parallelism - computation consists of lots of simple actions and behaviors going on simultaneously and asynchronously. And yet the language itself was so simple that it only took a few hours for a game artist to master it. In particular, artists did not need to learn the complex concepts of flow-of-control, recursion, iteration, and other features of imperative programming languages.</div>
<div>
<br /></div>
<div>
Another cool feature of Swarm was the way it handled reloading of source files: The Swarm interpreter would use the filesystem API to be notified whenever any files in the source directory changed. So all an artist had to do was hit Ctrl-S in their text editor, and immediately see their changes take effect. Typically artists would arrange their desktop so that the text editor and the game window were both visible side-by-side.</div>
<div>
<br /></div>
<h3>
Alternatives to scripting languages</h3>
<div>
<br /></div>
<div>
Scripting languages are often used to specify the behavior of objects within the game. However, an alternative which has frequently proved successful is to treat objects as bundles of properties, where the presence or value of a property influences the object's behavior. This means that instead of editing text files, the game developer uses a property editor - a UI widget that allows them to set the values of these properties from within the game.</div>
<div>
<br /></div>
<div>
Typically a property editor widget is generic and is driven by a schema definition. The schema definition contains a description of all of the properties a given object is allowed to have, and what the types and allowable values of those properties are. The type of a property determines what type of editor to use to edit that property - so a "string" property will generate a text input box, while a "color" property will generate a color picker widget.</div>
<div>
<br /></div>
<div>
An example of this is the building definitions in Sim City 4. There were many hundreds of different types of buildings, and each one had many dozens of properties such as zoning requirements, electricity consumption, flammability, and so on. The content producers who entered this data needed to have lots of domain knowledge about cities in order to create a city simulation that was appropriately believable.</div>
<div>
<br /></div>
<div>
Of course, the <i>interpretation</i> of these properties - such as how the flammability property influences the chance of the building catching fire, and how quickly the fire would spread - were coded in C++ as part of the game engine. But from a game production standpoint, the benefits of using properties was the same kind of rapid development afforded by scripting languages, but with far less complexity.</div>
<div>
<br /></div>
</div>Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-17237279135449750992012-07-11T02:23:00.000-07:002012-07-11T02:24:18.246-07:00Tart still on hiatus, but not deadI've been greatly enjoying working on my Android game project lately - here are some screen shots of my most recent progress: <a href="https://plus.google.com/102501415818011616468/posts/51UaQviTyfM">https://plus.google.com/102501415818011616468/posts/51UaQviTyfM</a><div> <br></div><div>Naturally this means that I haven't been doing any active coding on Tart for the past 8 months or so. However, that's not necessarily a bad thing. You see, even though I'm not actively working on it, it's still percolating in my subconscious mind, and occasionally an idea pops out. I've often found that some problems are best solved by stepping back and letting go for a while - sometimes the focus on solving a particularly vexing problem causes a kind of tunnel vision, while stepping back and getting some distance from the problem can lead to a new perspective on how to solve it - or even how to avoid it being a problem at all.</div> <div><br></div><div>I thought I would take some time to jot down some of the issues that I have been thinking about.</div><div><br></div><div>I think that there are some aspects of Tart for which I never quite had a clear design idea. That is, there were certain parts of the language design where I figured that I would fill in the blanks at a later time, and looking back on the project I realize that those areas never did get filled in properly. Worse, I realize that some of those design aspects should have been designed up front rather than being put off until later, because the design choices affect the compiler's output in a fairly fundamental way.</div> <div><br></div><div>1) Dynamic Linking</div><div><br></div><div>An example of this is dynamic linking of modules. Being able to divide an application into separately loadable chunks is fairly fundamental these days. Of course, at the lowest level we know how this is all supposed to work - the semantics of shared libraries and dynamic linking are well understood. But high-level languages need something more than just stitching together of linker symbols. They need to be able to do method calls across module boundaries, which means that the class definitions in the various modules must be interoperable. If two modules both import references to a particular class, those two class definitions must be combined somehow - otherwise you end up with two distinct classes that happen to have the same name, and instances of those classes will no longer be comparable, even though they may have identical values. </div> <div><br></div><div>In the past, the Tart compiler has generated a large quantity of static metadata for each class (dispatch tables, reflection data, GC stack maps, etc.), and relied on LLVM's linker to combine identical definitions. This is fine for static linking, but doesn't address the problem of dynamic linking at all. To address the problem of dynamic linking, a different approach is needed.</div> <div><br></div><div>My current thinking is to replace a lot of the statically defined data structures with one or more global registries. For example, you would have a global registry of types. Whenever a module is loaded which contains a reference to a type, it would look it up in the registry (by name if it's a named type, by type expression otherwise), and if the type exists then the module would use the returned value as the type pointer. If the type does not exist, then the module will contain a static string that is a serialized description of the type that can be used to construct the actual type object. In other words, the first module that uses a given type gets to set the definition of that type, and all other modules will use that definition.</div> <div><br></div><div>Note that the serialized description of the type could potentially be smaller than the instantiated type object, since there would be no need to store NULL pointers, and the serialized information could be compressed.</div> <div><br></div><div>Of course, this can lead to problems if two modules have incompatible definitions of a type. For example, two modules might not agree on the length or structural layout of the type. To solve this problem, we need to be able to check if two type definitions are compatible. A strict check is fairly easy - see if the definitions are identical. But strict checks lead to brittleness and versioning hell - ideally you want some flex in the system so that a dependent module can be modified without recompiling the world.</div> <div><br></div><div>A very flexible approach involves constructing the class dispatch tables at runtime instead of at compile time. This allows you to add or delete methods of a class and still remain compatible with old code. This works because the method offset into the dispatch table is no longer fixed at compile time, but calculated at runtime, so if the dispatch table slots change (because methods are added or removed) it won't break older code.</div> <div><br></div><div>One can go even further and use a dispatch map rather than an array, similar to what Objective-C does: For each method signature, you generate (at runtime) a selector ID. Calling a method involves looking up that selector ID in a hash map, which returns the actual method pointer. While this does cause some additional overhead for certain kinds of method calls, other types of calls (such as calls through an interface) might potentially be sped up.</div> <div><br></div><div>2) Debugging</div><div><br></div><div>Support for DWARF has been the bane of my existence, and has caused me more frustration than any other aspect of working on Tart. And to add insult to injury, almost all of the DWARF information is duplicative - that is, it's simply repeating information that's already present in the reflection data (such as a description of fields and methods of a class), but encoded differently.</div> <div><br></div><div>I recently learned, however, that lldb (the LLVM debugger project) can potentially support custom debugging formats. That is, it would not be impossible to write an extension to lldb that directly parses the reflection data of a module instead of using DWARF.</div> <div><br></div><div>This does mean, however, that source-level debugging would only work with lldb, and not gdb. That may be too much of a price to pay - for one thing, I like the Eclipse integration with gdb, and not being able to debug in Eclipse would be sad.</div> <div><br></div><div>3) The name "Tart"</div><div><br></div><div>I've never been completely satisfied with the name "Tart", but unfortunately all the good names are taken. However, I'm concerned about possible confusion or conflation with "Dart", which is yet another language that Google is trying to promote.</div> <div><br></div><div>Anyway, this is not a complete list of all the things I have been thinking about, but its late, and I shall leave the rest for another time.</div><div><br></div><div>-- <br>-- Talin<br> </div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-16691755763048796352011-12-25T22:56:00.001-08:002011-12-25T22:56:27.784-08:00Status updateIt's been a while since I've posted on my progress. I'm still in the "taking a break from Tart" mode, which is why you haven't heard from me lately. I plan to get back to working on it after the holiday. <div><br></div><div>In the mean time, I've been busy working on Mint, and things are going pretty well. Mint can not only build itself directly, but can also generate makefiles to build itself indirectly. The Mint source tree now has a "build.osx" directory which contains both the Makefile and header files needed for building Mint on OS X. The contents of this directory are generated entirely by Mint. There's also a "build.linux" directory which will (soon) have the same setup for Linux platforms.</div> <div><br></div><div>One of my design goals has been to make Mint useful for developers, even if their users don't have Mint installed on their systems. It would be hard to convince developers to use any new tool if it required all of their users to install that tool as well. Of course, Mint would be even <b>more</b> useful if the users had it installed, but first thing is to get some sort of momentum in the developer community.</div> <div><br></div><div>To that end, I've made it so that the Makefiles generated by Mint are position-independent, so that you can check them into the source tree along with your source files. In other words, a developer can use Mint on their personal workstation, and then generate Makefiles which can be invoked by the users who check out their sources, without those users having to install Mint themselves.</div> <div><br></div><div>Unfortunately, most projects need more than just Makefiles to build - they also need configuration scripts. For building on a foreign system, one can generally assume that something like 'make' exists, which means that one can use that as a common foundation. With configuration, however, that foundation is far less firm. There's autoconf, of course, which is built up out of shell scripts and m4 macros, but while most Unix-like systems have some version of autoconf installed, they may not have the <i>version</i> of autoconf that you need.</div> <div><br></div><div>I haven't quite figured out what to do about this, but there are a couple of different paths that could be explored. One idea would be to have Mint generate autoconf-compatible scripts; another would be to generate my own configuration scripts that were not autoconf-based. A third approach would be to not do configuration at all, but instead ship pre-configured Makefiles / build scripts for the most popular platforms.</div> <div><br></div><div>Ultimately, what I suspect developers want is a tool that will let them generate build scripts that will run on all of the platforms that they care about, while requiring the fewest number of additional tools or dependencies. So for example, it would be nice to press a button and get a Visual Studio project file, an XCode project, a Makefile for various platforms, and so on. The downside is that these pre-generated configurations can't cover every possible host environment, and so have to be configured for a least-common-denominator target environment.</div> <div><br></div><div>Of course, all of this is based on some assumptions about the users. 99% of users don't want to build from source in the first place - they want to install pre-compiled binaries. And a developer working alone doesn't need a fancy configuration and build system, when they can just add a new source file in their IDE and hit the rebuild button. The use cases where one checks out source and rebuilds it are fairly limited by comparison:</div> <div><ul><li>The case where a team of developers is working on a single project.</li><li>The case of a software packager who is creating a binary distribution.</li><li>The case where a project doesn't yet have an installation script or binary packages, so building from source is the only option for users.</li> </ul></div><div>For the first two cases, having to build and install Mint first is not that huge of a burden. For the last case, it makes me think that the really compelling use case for Mint is in the creation of installation packages. That is, if I could figure out how to get Mint to automatically generate a .deb or .rpm or a .dpkg, that would be something that I think developers would really be interested in. Heck, that's something I myself would be interested in, for Tart...hmmm, time to start reading the docs on building packages.</div> <div><br></div><div>Here are some links:</div><div><ul><li>Mint docs: <a href="https://github.com/viridia/Mint/wiki/Mint-Introduction">https://github.com/viridia/Mint/wiki/Mint-Introduction</a></li><li>Generated makefile example: <a href="https://github.com/viridia/Mint/blob/master/build.osx/Makefile">https://github.com/viridia/Mint/blob/master/build.osx/Makefile</a></li> </ul><div><br></div></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com1tag:blogger.com,1999:blog-2813257058440983072.post-74471556567567883792011-11-28T00:08:00.000-08:002011-11-28T00:09:01.541-08:00Mint progressAs I may have already mentioned, I decided to take a break from working on Tart, and spend a few weeks working on Mint. This should by no means be interpreted as a lack of interest or commitment in Tart. It's just that there are a number of difficult problems which have caused work on Tart to proceed with frustrating slowness. Most of these problems involve the complexities of generating DWARF debug info via LLVM's APIs, problems which I've already written about extensively and see no need to repeat here.<div> <br></div><div>In any case, I decided to give myself a holiday and work on something fun. And in fact the progress on Mint has been nothing short of astounding - I think I've written several hundred source files over the course of the last two weeks. (I've also been using Eclipse + EGit to do the coding, which has been a remarkably pleasant experience.)</div> <div><br></div><div>Those who want a quick overview of what Mint is can look here:</div><div><br></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><a href="https://github.com/viridia/Mint/wiki/Mint-Home">https://github.com/viridia/Mint/wiki/Mint-Home</a></div> </blockquote><br><div>(Click the 'code' link at the top of that page if you want to browse the source.)</div><div><br></div><div>Of course, part of why the work on Mint is proceeding so rapidly is that unlike Tart, Mint has virtually no dependencies - it is a self-contained program that doesn't depend on complex libraries or other open-source projects in order to work.</div> <div><br></div><div>At the present time, the "mint" program doesn't actually do anything <i>useful</i>. But it does do a number of things that are <i>interesting</i>.</div><div><br></div><div>For example, Mint is able to run simple 'configure' tests such as testing for the presence of a standard header file such as <malloc.h>. It does this by invoking the C preprocessor and then looking at the exit code. Note that these configuration tests are in no way "built in" - instead they are defined in the standard Mint library.</div> <div><br></div><div>A Python-inspired 'import' statement is used to import the configuration tests into your project's build file:</div><div><br></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"> <div><font class="Apple-style-span" face="'courier new', monospace">from prelude:configtests import check_include_file, check_include_file_cpp</font></div><div><font class="Apple-style-span" face="'courier new', monospace"><br> </font></div><div><div><font class="Apple-style-span" face="'courier new', monospace">HAVE_STDIO_H = check_include_file { header = "stdio.h" }</font></div><div><font class="Apple-style-span" face="'courier new', monospace">HAVE_STDBOOL_H = check_include_file { header = "stdbool.h" }</font></div> <div><font class="Apple-style-span" face="'courier new', monospace">HAVE_STDDEF_H = check_include_file { header = "stddef.h" }</font></div><div><font class="Apple-style-span" face="'courier new', monospace">HAVE_STDLIB_H = check_include_file { header = "stdlib.h" }</font></div> </div><div><font class="Apple-style-span" face="'courier new', monospace"><div>HAVE_CPP_ALGORITHM = check_include_file_cpp { header = "algorithm" }</div></font></div></blockquote><br><div>The syntax "<i>projectname</i>:<i>modulename</i>" syntax in the import statement is used to import definitions from another source tree - this is how Mint supports multiple source trees in a single build configuration. The name "prelude" is a special pseudo-project that points to the location of the Mint standard library.</div> <div><br></div><div>The Mint language tries to be as declarative as possible, describing the end result that you want to have accomplished, while hiding from view the steps needed to get to that end result. Although Mint does have functions, most actions are described by objects rather than function calls. The typical pattern in Mint is that instead of calling a function with N parameters, you would commonly define an object with N named properties, and then 'evaluate' that object to get a list of actions to perform.</div> <div><br></div><div>The advantage of this approach is that we can take the graph of objects and interpret it in different ways. If we want to actually build an executable program we would evaluate the object graph into a set of runnable actions for invoking compilers or other tools. On the other hand, if we want to generate an Eclipse or XCode project file, we would translate the object graph into an XML file that could be read into those programs.</div> <div><br></div><div>Going back to the above example, the "check_include_file" symbol refers to a prototype object. In Mint syntax, an expression of the form <i><prototype></i> { <i><properties...></i> } creates a new object with the given prototype. In this case, we're creating an object that inherits from the 'check_include_file' prototype, and specifying the name of the header file to test for.</div> <div><br></div><div>The 'configtests' module in the Mint standard library contains the definition of 'check_include_file'. Here's the actual definition (with comments stripped for brevity):</div><div> <br> </div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><font class="Apple-style-span" face="'courier new', monospace">exit_status_test = object {</font></div></div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> lazy param message : string = ""</span></div> </div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> param program : string = undefined</span></div></div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> param args : list[string] = []</span></div> </div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> lazy param input : string = undefined</span></div></div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> export lazy param value : bool =</span></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> console.status(message)</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> or shell(program, args ++ ["2>&1 > /dev/null"], input).status == 0</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div></div><div><div> <span class="Apple-style-span" style="font-family: 'courier new', monospace; ">check_include_file = exit_status_test {</span></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param header : string = undefined</font></div> </div><div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> message = "Checking for C header file ${header}..."</span></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> program = "cpp"</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> args = ["-xc"]</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> input = "#include <${header}>\n"</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div></div></blockquote><div><br></div><div>Here's a blow-by-blow explanation of this code:</div><div><br></div><div>"exit_status_test" is a generic prototype that performs configuration tests by running some shell program and checking the exit status. "check_include_file" inherits from, and further specializes, this prototype.</div> <div><br></div><div>A "param" declaration defines an object property. You can only assign values to properties that have been defined in a prototype - this is to avoid spelling errors.</div><div><br></div><div> A "lazy param" is one that is evaluated dynamically. That means that the value of the parameter is calculated each time the parameter is accessed (the normal behavior is to evaluate the value of the parameter at the time the value is assigned.) You can think of lazy params as equivalent to no-argument member functions.</div> <div><br></div><div>Understanding lazy parameters requires a careful understanding of Mint's scoping rules. First, Mint uses <i>lexical scoping</i>, like most modern languages. Mint also uses <i>object-oriented-style</i> lookup rules, meaning that properties defined on an object take precedence over properties defined on that object's prototype. So for example in the code sample above, we can see that the property 'header' is used in the calculation of the 'message' property of 'check_include_file'. Thus, if you tried to evaluate 'HAVE_STDIO_H.message', you'd get the value 'Checking for C header file stdio.h...". Even though 'message' is a property of 'check_include_file', when it gets evaluated the value of 'header' is taken from HAVE_STDIO_H, not 'check_include_file'.</div> <div><br></div><div>An "export" parameter is one that should be saved when writing out the build configuration. So for example, we want to save the result of our configuration test (so that we don't have to run it every time), thus the 'value' property is declared as 'export'.</div> <div><br></div><div>The 'program' and 'args' parameters are the name of the program to run, and the arguments to pass to it, respectively. In the check_include_file prototype, we see that the program to run is "cpp" (The C preprocessor) and the argument is "-xc" (which forces C dialect, as opposed to C++ or Objective-C).</div> <div><br></div><div>The "input" argument is used to specify text that is to be piped into the program's standard input. In this case, it's a single line which contains a #include of the header we're interested in.</div> <div><br></div><div>Finally, the 'value' property of 'exit_status_test' is where all of the actual work is done: It first prints a message to the console, and then executes a shell command using the built-in 'shell' function. (Ignore the 'or' in there - that's a temporary hack due to the fact that there's no statement blocks implemented yet.) The 'shell' function returns an object, which has several properties, one of which is the exit status.</div> <div><br></div><div>If you've gotten this far, I think you'll agree that the language is quite flexible, and that it should be relatively straightforward to create configuration tests of almost any imaginable sort.</div> <div><br></div><div>I'll show one more code example from the Mint standard library. Although Mint does not yet have the ability to do anything useful with build targets, it does at least allow build targets to be declared. The following is the (unfinished) prototype for build targets that generate executables, and what's notable about it that it can figure out from the source file extension what compiler to invoke. Moreover, this map of file extensions can be extended by objects that inherit from this prototype, making it possible to support other languages.</div> <div><br></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><font class="Apple-style-span" face="'courier new', monospace">object_builder = builder {</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param cflags : list[string] = []</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param cxxflags : list[string] = []</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param include_dirs : list[string] = []</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param library_dirs : list[string] = []</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param warnings_as_errors = false</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> param builder_map : dict[string, builder] = {</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "c" = c_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "cpp" = cpp_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "cxx" = cpp_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "cc" = cpp_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "m" = objective_c_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "mm" = objective_cpp_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "h" = null_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "hpp" = null_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "hxx" = null_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "lib" = identity_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "a" = identity_builder,</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> "o" = identity_builder,</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> export lazy param implicit_depends : list[builder] = sources.map(</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> src => builder_map[path.ext(src)] {</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> sources = [ src ]</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> })</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace"> actions = implicit_depends.map(b => b.actions)</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div> </div></blockquote><div><br></div><div>The interesting bit is in the calculation of the 'implicit_depends' property. This uses a Mint lambda function. The syntax for lambdas is "(args) => expr" or just "arg => expr" if there's only one argument. In this case, we're running a 'map' over the list of source files, and for each source file, we get the file extension, look it up in the dictionary, and return an object prototype. We then use that prototype to generate a new object using the "proto {}" syntax. So basically this generates a new builder object for each source file.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-19035618378699275262011-10-30T17:29:00.001-07:002011-10-30T17:29:26.603-07:00Thoughts on a build configuration languageWork on Tart is on hold for the moment while I am waiting to hear back from the LLVM folks about a bug in llc.<div><br></div><div>In the mean time, I want to write down a few notes about "mint", which is the name of the hypothetical future build tool that I want to create. Although my plan is to write mint in Tart, there's nothing Tart-specific about it, and it could be written either in C++ or Python or some other language.</div> <div><br></div><div>I've been thinking about this a lot lately, especially because there's a big discussion on llvm-dev about the future of the build system, and part of that includes some very passionate opinions about the pros and cons of cmake.<br clear="all"> <div><br></div><div>Anyway, here are some basic requirements for mint:</div><div><ul><li>It should be fast.</li><li>It should be extensible, especially with respect to 3rd-party tools. One should be able to write an extension module for yacc or antlr that makes it as easy to invoke those tools as it is to invoke gcc.</li> <li>It should support hermetic builds, so that a particular binary can be produced on a given host machine that is identical to one produced on another machine, even if those machines have different environments.</li><li> It should support generating project files for popular IDEs such as Eclipse, XCode, Visual Studio, and so on.</li></ul><div>I'd also like it to support automatic download of dependent packages, but unfortunately this is an area which I don't have a lot of experience in.</div> </div><div><br></div><div>So the basic idea is that the build configuration language (BCL) is a hybrid functional / declarative language that supports prototype inheritance.</div><div><br></div><div>The language is <i>declarative</i> in the sense that what it primarily does is describe a graph of objects, the Build Dependency Graph (BDG). Objects in the graph include targets, files, tools, actions, and other entities which are used in the build. Making the language declarative means that a build configuration file describes the relationships between these objects, but doesn't say how these relationships are processed or in what order - that is determined by whatever tool is actually doing the build. This is what makes it feasible to generate a project file for an IDE.</div> <div><br></div><div>The language is <i>functional</i> in that an object's properties can be expressions which are lazily evaluated. For example, the set of flags passed to a compiler is calculated from a number of different inputs, including the user's choices as to whether to enable debug symbols, assertions, and so on.</div> <div><br></div><div>Prototype inheritance allows for objects in the graph to be re-used. For example, when you declare a build target, you start by inheriting from an abstract build target prototype, and then fill in the details about your specific target. The abstract build target prototype knows about source files, output files, and dependent targets; your target fills in the details of what specific files are involved. Or you may choose to inherit from a build target prototype that knows how to invoke the C++ compiler, which saves you the trouble of having to write the command-line flags for the compiler.</div> <div><br></div><div>Because prototype inheritance is used so much in this language, the syntax is very simple:</div></div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"> <div><div><font face="'courier new', monospace"><prototype> { <properties> }</font></div></div></blockquote><br> <div>Where 'prototype' is some previously defined object, and 'properties' is a list of key/value pairs. So for example:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"> <div><font face="'courier new', monospace">myProgram = program.cpp {</font></div><div><font face="'courier new', monospace"> sources = [ "main.cpp" ]</font></div> <div><font face="'courier new', monospace">}</font></div></blockquote><div><br></div><div>Here we are starting with the standard prototype "program.cpp", and filling in the 'sources' slot ('sources' is defined in the prototype, but it's empty). We are then assigning that to the name 'myProgram'.</div> <div><br></div><div>We can then, if we wish, create a variation of 'myProgram' that is compiled with optimization:</div><div><br></div><div><blockquote style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:40px;border-top-style:none;border-right-style:none;border-bottom-style:none;border-left-style:none;border-width:initial;border-color:initial;padding-top:0px;padding-right:0px;padding-bottom:0px;padding-left:0px"> <div><font face="'courier new', monospace">myProgramOpt = myProgram {</font></div><div><font face="'courier new', monospace"> opt.level = 2</font></div><div> <font face="'courier new', monospace">}</font></div></blockquote><br></div><div>The "opt.level" property was also defined in the program.cpp prototype. The program.cpp prototype has a tool definition for the cpp compiler. Here's a glimpse of what the program.cpp prototype might look like, with many details omitted.</div> <div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="'courier new', monospace">program.cpp = program.base {</font></div> <div><font face="'courier new', monospace"> opt = dict {</font></div><div><font face="'courier new', monospace"> level = 0</font></div><div><font face="'courier new', monospace"> }</font></div> <div><font face="'courier new', monospace"> cflags = []</font></div><div><font face="'courier new', monospace"> tool = compiler.cpp {</font></div><div><font face="'courier new', monospace"> flags = [</font></div> <div><font face="'courier new', monospace"> match (opt.level,</font></div><div><font face="'courier new', monospace"> 0 => "-O0",</font></div> <div><font face="'courier new', monospace"> 1 => "-O1",</font></div><div><font face="'courier new', monospace"> 2 => "-O2",</font></div> <div><font face="'courier new', monospace"> 3 => "-O3",</font></div><div><span style="font-family:'courier new', monospace"> * => raise("Invalid optimization level: " ++ opt.level))</span></div> <div><font face="'courier new', monospace"> ] ++ cflags</font></div><div><font face="'courier new', monospace"> }</font></div><div><font face="'courier new', monospace">}</font></div> </blockquote><br><div>The first few lines define a property called 'opt' whose value is a dictionary type - basically just a namespace. Within that is the property 'level', which defaults to zero. (I'm undecided as to whether 'level' should have a type as well as a default value - it wouldn't make sense to assign a string to 'level'.)</div> <div><br></div><div>Next we have the tool that will get run when this target gets updated. The "flags" property is a list of flags that gets passed to the compiler on the command line. When the compiler is invoked, each element of 'flags' will get evaluated and transformed into a string. That string is then passed to the compiler as the shell arguments.</div> <div><br></div><div>In the case of opt.level, we use a match expression to transform the optimization level numbers 0..3 into compiler flags of the form -On. The idea here is to abstract away the specific syntax of the compiler's command-line arguments, so that the same syntax can be used to control different compilers.</div> <div><br></div><div>There is also a 'cflags' property that can be overridden by descendant objects, allowing flags specific to a particular compiler to be passed in.</div><div><br></div><div>The main idea here is that "builtin" compilers for C and C++ use the same descriptive syntax as for 3rd-party extension compilers. In other words, the built-in rules aren't special.</div> <div><br></div><div>Another kind of prototype is used to define the command-line options to the build script itself:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"> <div><font face="'courier new', monospace">enable-asserts = option {</font></div><div><font face="'courier new', monospace"> type = bool</font></div><div> <font face="'courier new', monospace"> default = false</font></div><div><font face="'courier new', monospace"> help = "Whether to enable assertion checks"</font></div> <div><font face="'courier new', monospace">}</font></div></blockquote><br><div>This means that the user can type "mint --enable-assertions" to generate a build configuration with assertions enabled. Or even type "mint --help" to print out the various options available.</div> <div><br></div><div>BTW, one thing that would be neat is if "--enable-assertions" could change just that one option, while leaving other options set to their current values.</div><div><br></div><div>Anyway, I'd be curious to know what people think of this idea.</div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-78240463058487128872011-10-18T15:31:00.001-07:002011-10-18T15:31:27.786-07:00JIT / AOT HybridsSomething I've been pondering a lot lately is the notion of link-time code generation. <div><br></div><div>The Tart compiler generates a lot of synthetic data and code, compared to a language like C++. This includes reflection tables, stack maps for garbage collection, type adapters, and so on.</div><div><br> </div><div>What I've been wondering is whether it would make sense to do this work in the linker rather than in the compiler. There's even a precedent for this: there's one data structure which is already generated at link time, which is the list of static roots - global data structures that need to be traced in the collector.</div> <div><br></div><div>There's a variety of things that could be generated at link time, ranging from the "only slightly ambitious" such as interface dispatch methods, to the "wildly ambitious" such as generating DWARF debugging info or even instantiating templates.</div> <div><br></div><div>In order to do any of this, the linker would need much more information about high-level data structures and types. Ironically, this information - basically a serialized form of the AST - is already generated by the compiler and stored in the module. This information isn't currently used by the linker - instead, it's used by the compiler to allow already-compiled module files to be imported, without having to have the original source files.</div> <div><br></div><div>If we take this idea to it's logical extreme, what we end up with is something like a Java class file that's compiled ahead of time (AOT), instead of just in time (JIT). That is, you have a single, comprehensive encoding of all of the types and methods in the module, and this encoded information is then used to produce the reflection tables, tracing tables, dispatch tables, and DWARF debug info. (As opposed to what it does now, which is to generate all of these tables separately, at compile time, and then glue them together in the linker.)</div> <div><br></div><div>This whole approach basically blurs the line between AOT and JIT compilation, in that the inputs to the linker look a lot like the inputs to a VM.</div><div><br></div><div>There's some problems to solve however.</div> <div><br></div><div>1) One problem with using the serialized AST is that lacks a lot of information, since it hasn't been fully analyzed. Type names in the AST are just names - we don't know yet which type is the one being referred to. Similarly with methods and variables, all we know is the name at this point. The largest part of the compiler is the part that analyzes the AST and converts it into a CFG (Control flow graph) in which all types are resolved, template parameters expanded, and so on. We don't want all of this functionality to live in the linker - instead, we want the compiler to do the analysis and then pass to the linker the results of that analysis.</div> <div><br></div><div>So the first problem to be solved is to come up with a way to serialize the CFG rather than an AST.</div><div><br></div><div>2) A second problem has to do with template instantiation. Currently templates are not analyzed until after they have been instantiated. The reason for this is that until they are analyzed, templates don't have enough information to be able to do a successful analysis.</div> <div><br></div><div>As a simple example, take the max() function whose declaration is "def max[%T](a:T, b:T) -> T". This function requires that it's template parameter, T, have a less-than operator defined for it. If there's no less than operator, the template instantiation fails. Until we actually attempt to instantiate the template and bind some type to T, we don't know if there's a less than operator defined or not. That's why templates are written out as un-analyzed ASTs, rather than fully-analyzed CFGs.</div> <div><br></div><div>To solve this problem, we would need to change the way template parameters work. In order to do any operation on a variable whose type is a template parameter, you would have to declare the template parameter as supporting that operation.</div> <div><br></div><div>Say we have a template parameter T, and we have some value 'a' whose type is T. Now we want to call 'a.toString()'. In the current system, we don't know whether a has a toString() method or not, but if we attempt to instantiate the template with some type that doesn't have a toString() method, then an error will occur. In the new system, in order to call a.toString(), you would have to declare template parameter T as [%T <: HasToString], where 'HasToString' is a protocol type that includes a 'toString()' method. In other words, having a 'toString()' method is now an explicit requirement for parameter T, any attempt to instantiate the template with a type that doesn't have a toString() method will fail early.</div> <div><div><br class="Apple-interchange-newline">(FYI - in the literature on type theory, what I have described corresponds to "parametric polymorphism" whereas the way things work now is "ad-hoc polymorphism".)</div> </div><div><br></div><div>Unfortunately, Tart's protocol system only works on instance methods, not on regular functions. Right now there's no way to express the concept "match any type that has a less-than operator defined for it". In other words, what we would need is some way to say "given a type T, return true if there is a function 'def infixLessThan(:T, :T) -> bool' defined somewhere." At the moment, I can't even imagine what that syntax would look like. But for now, let's assume we come up with some way to do this.</div> <div><br></div><div>By pre-declaring what methods we need, we can do the analysis passes on the template and create a CFG. This CFG won't actually be complete, because some types are still not known. But we can at least do enough analysis to be able to write the CFG out to a file.</div> <div><br></div><div>3) Currently, you can link Tart programs in two ways: Either by using the Tart linker, 'tartln', or by using the standard LLVM tools (llvm-ld, opt, and llc). If using the latter, however, you need to load in the Tart-specific plugins for reflection and garbage collection.</div> <div><br></div><div>In order to do the link-time code generation that I'm describing, we would need to put all of the code to do that into the shared library, so that it can be loaded as a plugin as well.</div><div><br> </div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-88981271748348788912011-10-11T22:40:00.001-07:002011-10-11T22:40:46.890-07:00Another idea on mutabilityI was thinking about the way that 'const' gets used in C++ programs. In particular, it's extremely tedious work to take a body of source code that doesn't use 'const' and refactor it to be const-correct. Typically what happens is you add 'const' modifiers to a small section of the code, and then try to compile, at which point you get a jillion errors. You then go and fix up all of those errors to be const-correct, try to compile, and now you have a jillion-squared errors.<div> <br></div><div>(Of course, this tends to be more true for some uses of const than others - it depends on how widely referred-to is the thing that you are making const.)<br><div><br></div><div><div><div>In other words, because const is so viral in C++, you end up having to convert your entire program in one go - there's no easy way to break up the change into manageable chunks.</div> </div></div></div><div><br></div><div>So I wonder if it makes sense to give programmers a "soft landing" option, in which const-correct and const-incorrect code can interoperate without creating a ton of warnings. There are of course some serious downsides to this idea. The fact that the C++ compiler tells you exactly what values you need to add the 'const' modifier to is pretty useful. And allowing programmers to write non-const-correct code means a loss in safety.</div> <div><br></div><div>BTW, all of this started because I was trying to figure out how to write the following function:</div><div><br></div><div><font class="Apple-style-span" face="'courier new', monospace"> def tracePointer[%T <: Object](v:T);</font></div> <div><br></div><div>The <: operator means "isSubtype" - basically it's saying that the T parameter must be type Object, or a subtype of Object - it can't be an int for example.</div><div><br></div><div> The problem is that this fails if you attempt to bind T to "readonly(Object)". The reason is because "Object" means the same as "mutable(Object)", which is a specialization of "readonly(Object)". From the compiler's point of view, mutable(Object) <: readonly(Object), not the other way around.</div> <div><br></div><div>Unfortunately, while this makes sense from a theoretical point of view, it fails the practicality test. When you say "A <: B", with no mutability qualifiers on either A or B, what you generally mean is "type A is a subtype of type B, and I don't care what the mutability modifiers are". If you'd explicitly given a mutability modifier, like "A <: mutable(B)", that would be an entirely different story.</div> <div><br></div><div>Since one of the design rules of Tart is that practicality should dominate over theoretical purity, I put in a temporary hack that basically says "when using the subtype operator, if neither side of the expression has an explicit type qualifier, then don't consider the type qualifiers of the values they are bound to when doing the comparison." However, this hack is rather ugly, and is yet one more thing to remember when programming in Tart.</div> <div><br></div><div>A different, and much more radical idea is this: That a type name with no mutability qualifiers ("Object") doesn't mean "mutable" like it does now. Instead, it means "mutability unspecified", in other words there are no guarantees about mutability or immutability at all. So the hierarchy would look like this:</div> <div><ul><li>(no qualifier)</li><ul><li>readonly</li><ul><li>mutable</li><li>immutable</li></ul></ul></ul><div>Basically it means that you can implicitly convert from (no qualifier) types to readonly, mutable, or immutable types and the compiler won't complain. So upcasting is implicit and silent - downcasting (converting from (no qualifier) to a qualified type) requires an explicit cast.</div> </div><div><br></div><div>What this means is that a lazy programmer can write code without thinking about mutability at all - they just don't use the mutability qualifiers in their code. If at some future point they decide that explicit mutability is a good idea, they can go and start adding the keywords where they are needed. Unfortunately, the compiler won't be as helpful as it would be in the case of C++ - if you forget to add the keyword in some places, the compiler won't always detect that, since it's legal to convert from readonly(Object) to Object without an explicit cast.</div> <div><br></div><div>It also means that the expression "T <: Object" now says exactly what we intuitively think it ought to mean.</div><div><br></div><div>This is an interesting idea, but I think it goes a little too far, in that it does more than just allow the programmer not to be distracted by mutability concerns - it *actively encourages* programmers to write code that doesn't address mutability issues by making such code much cleaner-looking and easy to type. You see, I think that the easiest option should also be the correct one - that is, you can break the rules if you want, but if you follow the rules you'll not only get the satisfaction of having correct code, but you'll also get clean-looking, succinct code as well.</div> <div><br></div><div>Unfortunately, with mutability this is hard to do - making the compiler smart enough to guess the correct default without the programmer having to explicitly type it means making the rules of the language much more complicated and hard to remember.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-91031851629695852362011-10-11T16:35:00.001-07:002011-10-11T16:35:49.424-07:00Tart status update<span id="goog_1558692965"></span><span id="goog_1558692966"></span><a href="/"></a>I decided to back off on the "make function parameters default to read-only" change because it was getting too big and too complex. I still plan to go ahead with it, but I need to fix some other things first. The whole mutability thing has introduced a lot of small problems that need to be solved one by one, and I've just been working through them.<div> <br></div><div>One question that has come up is: If function parameters are read-only by default, should function return values also be? I even thought about making all object references readonly by default, but I really don't want to drink quite so deeply from the functional programming kool-aid.</div> <div><br></div><div>Another question that keeps rolling around in my brain is this: Was it the right choice to make Tart an AOT (Ahead of Time) language instead of a JIT? I originally made tart an AOT because I was looking for a replacement for C++, not another Java. And AOTs do have a couple of obvious advantages: quicker startup time, for example.</div> <div><br></div><div>VM-based languages, however, have plenty of advantages of their own. For example, in the current incarnation of Tart, up to 4 different versions of a class can be written to an output file: Once as executable code, once as DWARF debugging info, once as reflection data, and once as importable symbols for compilation of another module. The reason that these 4 different representations are necessary is because any of the last three can be deleted from the module without affecting any of the others - so for example you can strip out all the DWARF and reflection will still work. With a JIT, we'd only need to write a single representation, and then produce on demand any or all of those representations as needed. And the whole "dynamic linking" problem completely disappears.</div> <div><br></div><div>Similarly, a JIT can make all kinds of optimizations that are not available to an AOT compiler. For example, if it knows that class A is never subclassed (because no such class has been loaded into memory), it can optimize calls to A's methods as direct calls rather than dispatched through a jump table. Of course, how much optimization you get depends on how long you are willing to wait at startup.</div> <div><br></div><div>One could, in fact, design an intermediate representation that would allow better optimizations than C++, Java, or even LLVM IR, because it would preserve certain high-level invariants that could be used to guide optimizations that are normally removed from byte-code representations. (Note: This means that the "compiled" class files would not be LLVM bitcode files, but some higher-level representation.)</div> <div><br></div><div>Writing a JIT for Tart wouldn't be all that hard, if we used LLVM's JIT engine as a base. And it would be fun. On the other hand - it would be completely, recklessly <i>insane</i>. Therefore I won't do it. That doesn't prevent me, however, from <a href="https://docs.google.com/document/d/13nhftC8RberTfVPk-fpFOYKmVqSrxnu8ggO9ALtVa1k/edit?hl=en_US">writing a design doc about it</a>.</div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-25295488431677598572011-10-05T16:33:00.001-07:002011-10-05T16:33:23.864-07:00Tart status updateI was out of town most of last week, and didn't get too much done on Tart. However, now that I'm back I'm continuing to work on type qualifiers and mutability.<div><br></div><div>Tart now allows type qualifiers (readonly, mutable, immutable) to be bound to a template parameter. The syntax looks like this:</div> <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">def somefunc[%Mod(?)](arg:Mod(Object)) -> Mod(String);</font></div> </blockquote><div><br></div><div>Basically what we're saying here is that "Mod" is essentially a function that operates on types - that is, it takes a type as input, and returns a modified type as output. Moreover, the type inference engine can deduce what kind of function it is by examining the context in which the function is used. If 'arg' is an immutable object, then "Mod(?)" gets bound to "immutable(?)", which in turn causes the result of the function to be immutable as well.</div> <div><br></div><div>More generally, each place where "Mod" appears in the function definition is a constraint. Function arguments are contravariant, so the type of 'arg' must be a subtype of Mod(Object). Function return values are covariant, so Mod(String) must be a subtype of whatever variable or parameter the return value is going to be assigned to. Given those two constraints, the compiler attempts to find a definition of Mod that satisfies both.</div> <div><br></div><div>One downside of the current syntax is that it doesn't let you choose <i>which</i> type qualifiers the parameter is bound to - which is not a big issue right now, because a type currently can only have one qualifier, but may be an issue in the future.</div> <div><br></div><div>Other than that there's not much to report. I still need to update the exception handling code to work with the new LLVM exception stuff, I just haven't gotten to it yet.</div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-37027334897560473742011-09-23T22:16:00.001-07:002011-09-23T22:16:30.029-07:00Type qualifiers, resolutionI realized that in the discussions about type qualifiers (which were very helpful), I had forgotten to add a note describing what I had finally decided to do about them. Here's the specification I've come up with:<div> <br></div><div>First off, there are 4 keywords used to indicate a qualified type: mutable, immutable, readonly, and adopted.</div><div><ul><li>"readonly" means that you can't change it, but someone else might. Readonly is considered to be a generalization (supertype) of both mutable and immutable, in that it provides guarantees that are strictly weaker than either.</li> <li>"mutable" indicates that you can modify the value. You can coerce mutable values to readonly values without an explicit type cast.</li><li>"immutable" means that no one is allowed to modify the object. You can coerce immutable values to readonly values without an explicit type cast.</li> <li>"adopted" is used to extend the first three qualifiers (mutable, immutable. readonly) to other objects. Normally when you declare an object reference to be immutable, that immutability only extends to data which is actually embedded within the object - it does not extend to objects that are pointed to by the object. So an immutable object can contain a reference to a mutable object. However, when an object "adopts" another object, that means that the adopted object gains the same type qualifiers as the adopting object.</li> <ul><li>An example would be a linked list class, which consists of a list header object, and list nodes. By declaring the node references in the header to be adopted, it means that if you make the list header readonly, then all of the list nodes become readonly as well; Conversely, if you make the list header mutable, then all of the list nodes become mutable.</li> </ul></ul></div><div>These keywords can be used in several ways:</div><div><ul><li>All 4 keywords can be used to modify a type, for example "immutable(ArrayList)".</li><ul><li>Note that adding a qualifier to a type does not actually create a new, distinct type. Mutability / Immutability is really an aspect of the reference to a type, not the type itself.</li> <li>For example, if you have a mutable ArrayList and an immutable ArrayList, and you call getType() on them, it will return the same value for both.</li><li>You cannot qualify an inherited type. You can't say "class MyList : immutable(List) { ... }".<br> </li><li>You can, however, pass a qualified type as a template parameter and it will retain it's qualifier. That means that List[int] and List[immutable(int)] are distinct types.</li><ul><li>Although I am wondering if this should be true...does it make sense to cast List[int] to List[readonly(int)]? Making the two be the same type would cut down on some level of template bloat...</li> </ul></ul><li>"mutable" can be used as a modifier on variable declarations, such as "mutable var foo". It means that the variable can be mutated even if the enclosing class is readonly. Normally variables have the same mutability as the enclosing class. (Since 'let' is used to indicate a field that cannot be changed, there's no point in allowing readonly or immutable as a variable modifier.)</li> <ul><li>Note that both 'mutable' (when applied to a variable) and 'let' only extend to data which is inside the field itself, in other words, the range of addresses that are covered by the field. So a reference to an object may be immutable, but that says nothing about whether the object being referred to is immutable. However, you can easily add an immutable qualifier to the object type as well. So for example "let e:immutable(List)" declares an immutable reference to an immutable list.<br> </li></ul><li>"mutable" can also be used on a function parameter declaration. All parameters are readonly by default.</li><li>"mutable" can be used as a modifier on a property getter (declared with "get"), to indicate that reading the property has externally visible side-effects.</li> <li>"readonly" can be used as a modifier on a method declaration ("readonly def foo() -> int"), which means that the method can be called even if the object is readonly or immutable. Such methods cannot modify any fields of the object, except those that have been explicitly declared to be mutable. Methods are considered mutable by default, except for property getters which are readonly by default. You cannot declare non-member functions to be readonly.</li> <li>"readonly" can also be used as a modifier on property setter definitions (declared with "set"). This would only make sense if the value of the property was stored externally to the object.</li><li> "readonly" can also be used as a class definition modifier "readonly class Foo", which simply causes all of the methods of that class to be considered readonly methods. This should not be taken to mean that objects of that type are readonly, merely that readonly is the default for methods of that class. (Making a class immutable is more a matter of insuring that it has no mutable fields.)</li> <li>"readonly", "mutable" and "immutable" can also be used to modify a value, as in "mutable(x)". This has the effect of a type cast for that value. Note that while it is legal to explicitly convert a mutable to immutable object, and vice versa, there is no guarantee that this will actually work - that is, if you cast a mutable value to immutable, it still might be changed by someone who kept a reference to the original mutable object; And if you cast an immutable object to mutable, you still might not be able to modify the object (it might be stored in protected memory.)</li> </ul><div>-- </div></div><div>-- Talin<br> </div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com1tag:blogger.com,1999:blog-2813257058440983072.post-68072662234263925402011-09-22T23:44:00.001-07:002011-09-22T23:44:25.846-07:00Some Metaprogrammatic MusingsOne of the motivations for creating the Tart language was my interest in metaprogramming. One thing I've noticed is that there's a kind of parity between metaprogramming and reflection - that is, both tend to be used to accomplish similar goals, but the former does it at compile time, whereas the latter does it at runtime. And both techniques have space costs - metaprogramming's cost comes from template bloat, whereas reflection's cost comes from all of the static metaclass information that has to be emitted by the compiler. <div><br></div><div>An example of this parity would be testing mocks. Libraries like mockito use reflection to generate mock implementations - that is, you feed it an interface, and it returns back an object that implements that interface - but the implementation is merely creating a record of all calls and parameter values. One could imagine a metaprogramming approach to the same problem - given an interface, produce at compile time a recording implementation.</div> <div><br></div><div>One trick that D has that makes metaprogramming easier is the 'static if' construct - having an if that is guaranteed to be evaluated at compile time makes it easier to write functions that are compile-time recursive. An example would be a template that takes a variable number of template parameters - this expands to a template that does something with the first type parameter, and then recursively expands itself with the tail of the type parameter list.</div> <div><br></div><div>However, I was thinking today, why not a static 'for each' loop? Assume you have a sequence of types whose length is known at compile time. One example is a variadic template - another is tuple types. One could construct a for loop which would iterate over the types in the sequence. Rather than actually looping, what the compiler would do is unroll the loop - that is, for a sequence of N types, what you get is the inner body of the loop replicated N times, each time with a different type parameter.</div> <div><br></div><div>An example of where this might be useful is in declaring production rules for a parser. Say we have a template "Sequence[%T...]" which takes a variable number of type arguments, where each type argument represents a matcher for some input. So you could do something like:<br> </div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">class Sequence[%Matchers...] {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> static def match(in:TokenStream) -> bool {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> for M in Matchers {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> if not M.match(in) {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> return false;</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> return true;</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div></blockquote><div><br></div><div>So if I invoke the template with something like "Sequence[Number, Identifier, Literal['if']]", what this turns into is code that calls Number.match(), followed by Identifier.match(), and so on. Of course, you can do something similar with object instances instead of types. Instead of "Sequence" being a type, instead it's just a function, and the matchers being passed into it are matcher objects, not matcher types. Again, it depends on whether you want to process this stuff at compile time or run time. (Notice, for example, that the 'match' function of class Sequence is static - no need to create any objects at all.)</div> <div><br></div><div>Interestingly, this starts to look a little bit like Haskell Monads, which makes me think of another thing: Tart allows overloading of operators, but one operator that is not even defined is "juxtaposition" - that is, putting two expressions next to each other with just whitespace between them. The Haskell "do" statement takes a series of expressions, where each expression is processed by the monad, and the result of that processing is the context for the next expression in the series. The idea of an imperative sequence - that is, a set of steps done in order - is only one possible way to use this. It could just as easily represent a dependency graph, a decision tree or any other idea where you have some chain of ideas, each idea building on the previous one.</div> <div><br></div><div>One can easily simulate this in Tart (or C++ for that matter) by operator overloading, with the downside that the syntax is not as compressed - so "number >> ident >> literal" could do exactly what "seq(number, ident, literal)" does. The question is, is it worth thinking about an even more compact syntax such as maybe "Sequence :: number ident literal", where you have some prefix (Sequence) that sets up a context, and that context let's you juxtapose the items, getting rid of the operators between the terms of the expression.</div> <div><br></div><div>Anyway, this is all just speculation for the moment, I don't have any concrete plans to change the language in this direction.</div><div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-18228459691132060002011-09-18T22:58:00.000-07:002011-09-18T22:59:09.911-07:00Type qualifiers and method paramsSo I'm not terribly happy with the current syntax for specifying readonly function arguments. <div><br></div><div>I'm finding that in practice, a large percentage of all function arguments are readonly. This is no surprise - many functions take arguments that they don't modify. Unfortunately, this means that if you add the readonly qualifier to all of the places where it should go, the word "readonly" then appears in dozens if not hundreds of times in a typical source file. It makes function signatures considerably longer. It also violates one of my design principles, which is that the things that "stand out" visually in the code should be the things that are most important to the reader. In the case of a function declaration, the most important thing is the parameter type, and I find that adding readonly(Type) everywhere makes the parameter type less visually pronounced.</div> <div><br></div><div>I have two ideas for solving this. The first idea is to make all function parameters readonly by default. That is, if you plan on mutating a function parameter, you'll have to explicitly declare it mutable. It turns out that if you do this, there's only a very few functions which require the mutable qualifier. This is good, because it really brings to your attention the fact that the parameter is somehow different from other parameters.</div> <div><br></div><div>(I should clarify something - we're not talking about mutating the parameter, but rather the thing the parameter points to. So a parameter like "dst:mutable(char[])" means that you're allowed to set elements in the array. The parameters themselves are always mutable, although Tart will notice if the parameter is never assigned to, and will enable certain optimizations if that is the case.)</div> <div><br></div><div>A different idea is to make a shortcut syntax for readonly. To fit within Tart's conventions, it should be a suffix. I was thinking something along the lines of "Type|r". I know that looks kind of weird - but then I was thinking, what if the "|" operator really meant "filter"? After all, that's kind of what "readonly" does - given an interface, it filters out (makes unavailable) all of the methods that would mutate the object. What if there were other kinds of filters? Not that I have any specific ideas for such.</div> <div><br></div><div>My meta-theme here is that syntax should follow Claude Shannon's law of information, which in this case I interpret as "the more unexpected an event is, the more information it contains". The most common case contains the least information, and the notation for expressing that case should be terse. OTOH cases which are rare contain more information, and therefore should take up more space on the page.</div> <div><br></div><div>This is part of the justification for having a shortcut syntax for array types (foo[]) and array literals ([1, 2, 3]). The three most commonly used containers are arrays, linked lists, and maps. These three account for something like 95% of all collections used in programs. I think that all three of those should have shortcut syntax, for the simple reason that they are so common.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-10031814794729947622011-09-18T22:28:00.001-07:002011-09-18T22:28:32.912-07:00Tart status updateI've been working on type qualifiers (mutable, etc.). This is a pretty large change, so I've been doing it in stages - I think there's been about 6 commits so far. Thank goodness for unit tests.<div><br></div><div> I'm also in the process of migrating the "failure" tests into the unit tests. Currently the failure tests work like this: There's a source file which contains example code which has errors in it - stuff that is supposed to fail. Each code snippet is preceded by a comment which contains a portion of the expected error message. The testrunner app attempts to compile each code snippet, and then compares the error messages produced with the comment.</div> <div><br></div><div>The failure tests have not been updated in a long time. I've decided to get rid of the test runner - instead I have a new TestCompiler class that accepts the source code as a string, and which has various methods such as expectSuccess(), expectFailure(), expectWarning(), which integrate nicely with the Google test framework. This allows success tests and failure tests to be grouped together in the same source file, which should make it easier to maintain the tests. So far, about half the failure tests have been converted over. Here's a sample of what the tests look like:</div> <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_FAILURE("class Test { adopted var test:int; }", "declaration modifier");</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_FAILURE("class Test { readonly var test:int; }", "Use 'let'");</font></div></div><div><div> <font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_SUCCESS("class Test { mutable var test:int; }");</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_FAILURE("class Test { immutable var test:int; }", "Use 'let'");</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_FAILURE("class Test { adopted let test:int; }", "declaration modifier");</font></div></div><div><div> <font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_WARNING("class Test { readonly let test:int; }", "are always");</font></div></div><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_FAILURE("class Test { mutable let test:int; }", "cannot be declared");</font></div> </div><div><div><font class="Apple-style-span" face="'courier new', monospace">EXPECT_COMPILE_WARNING("class Test { immutable let test:int; }", "are always");</font></div></div></blockquote><div> <br></div><div>The first argument is the source code to compile, and the second argument is the expected error message, or a portion of it.</div><div><br></div><div><div>I also took a bit of a break and added BitArray to tart.collections, with unit tests. That was fun to write.</div> </div><div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-76523140467044490102011-09-16T15:07:00.001-07:002011-09-16T15:07:59.831-07:00Discussions of Tart on RedditThanks to Keir for pointing this out to me - apparently a bunch of folks on Reddit have discovered Tart, and there's a <a href="http://www.reddit.com/r/programming/comments/kfvm7/tart_a_stronglytyped_general_purpose_programming/">whole lot of comments</a> - mostly negative, which is to be expected at this stage.<br clear="all"> <br> <div>The good news (for me anyway), is that there aren't too many surprises - most of the points being brought up are things I have spent a long time considering. That doesn't mean that I should dismiss these points out of hand, however.</div> <div><br></div><div>I see that there are a number of complaints which recur frequently in that thread. One is about the retention of "null" in the language - the so-called "billion dollar mistake". I've <a href="http://machinewords.blogspot.com/2009/12/problem-with-null-pointers-is-that-they.html">written about this before</a> - getting rid of null gets rid of some good things as well as some bad. I think that the best I can hope for is to reduce the need for null in most cases, without getting rid of it entirely. Disjoint types goes a long way towards removing the need for null, but they are not appropriate for every situation. A prime example is an array of object references - you have to initialize the array elements to <i>something</i>, and whatever that something is (null or void or sentinel object whatever) is going to cause an exception if you use it incorrectly. (You could enforce that arrays can only contain "optional" types - but that makes arrays a pain to use. You could always require a specific "fill value" for new arrays - but that also makes arrays a pain to use. Or you could do what many functional languages have done and just ban arrays altogether, so that everything ends up being cons'd lists.)</div> <div><br></div><div>Another recurring theme in the thread is the lack of concurrency primitives in the language. My response to that is there are a lot of languages which do quite well on multiprocessor systems without having concurrency baked into the language itself. Most of the languages that I have seen which do have syntactical support for concurrency also constrain the programmer to one particular style of concurrent programming - message passing, immutable shared state, actor models, and so on. I would much rather make a language that is flexible enough to let users of the language define such constructs for themselves, and let them compete in the marketplace until there is a clear winner.</div> <div><br></div><div>Lack of libraries: This is a feature, not a bug. One of the things that makes Tart so much fun to work on is the blank slate - total freedom from all those irritating library decisions made by Sun Microsystems, Microsoft, or the C++ standards committee. Also, having multiple return values and disjoint types has a dramatic impact on library APIs, so you wouldn't want to be shackled to the old libraries anyway. (That being said, it should be easy to call external libraries like zlib - expecting the entire world to re-write everything in your language is unrealistic to say the least.)</div> <div><br></div><div>More generally, the kind of people I'd most like to attract right now are people who enjoy writing libraries.</div><div><br></div><div>Garbage collection: Tart doesn't actually force you to use garbage collection, however, the presence of GC has a huge impact on the design of the standard library - for one thing, a big part of the design of any nonGC API is object lifecycle management, and that problem just goes away with GC. And since I'm not ambitious enough to write two standard libraries (one with GC and one without), I'll leave that as an exercise for whoever wants it badly enough.</div> <div><br></div><div>There's a lot of complaints about syntactical choices, which I really can't respond to, since that's mainly a matter of personal preference. The only thing I will say is that I have specific theories about how much punctuation a language ought to have in order to maximize readability - neither too much nor too little. The easy recognition of a particular piece of code not only depends on the actual letters and symbols themselves, but also the shape of the code as it is laid out on the screen. (Exercise for the reader: Take a sample of code, and replace all letters with 'x' - can you still get a rough sense of the structure of the code?)</div> <div><br></div><div>In any case, the important thing for me is not to get discouraged by negative comments - it's easy to point out flaws, more difficult to make positive contributions. And there are many areas where I could be convinced to change my mind with a sound enough argument.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-40178672064691803692011-09-14T13:17:00.000-07:002011-09-14T13:18:10.259-07:00VolatilityThe "volatile" type modifier presents an interesting problem.<div><br> </div><div>From what I understand, "volatile" is only meaningful on l-values - something like "(volatile int) 1" doesn't make a lot of sense. Unfortunately, when you pass a type to a template as a template parameter, you don't always know whether the template is going to use the type as an l-value or not. So for example if you wanted to create something like "List[volatile(int)]", we would have to allow the "volatile" qualifier on any type, l-value or not - it would basically be a no-op in most cases.</div> <div><br></div><div>The other approach is to say that "volatile" is an attribute of a variable or field, rather than being an attribute of a type. This makes more sense, but the downside is that you can no longer pass it as a template parameter. Thus, in order to have an array of volatile ints, you have to create a special VolatileArray[int] class, which is an exact clone of Array except for adding the volatile qualifier to the array's internal member declarations.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-70319718349143873972011-09-11T00:37:00.001-07:002011-09-12T15:38:42.268-07:00Article on adding type constructors to JavaSo I recently saw <a href="http://www.jot.fm/issues/issue_2008_06/article2.pdf">this article</a> on <a href="http://lambda-the-ultimate.org/">Lambda the Ultimate</a> about adding type constructors to the Java language. I have to admit, it took me several re-readings of the article before I understood the gist of what they were saying. And there are some parts of the paper, such as the logical proof, that I have no hope of understanding, as I just don't have the background.<br />
<div>
<br /></div>
<div>
<div>
<div>
Nevertheless, I understand it well enough I think. What they are talking about is indeed highly abstract and powerful. I'll try and summarize as best as I can: A type constructor can be thought of as a function that operates on types. An example would be "X => List[X]" - a function which, given a type X, returns the type of a list of X.</div>
<div>
<br /></div>
<div>
Where this gets powerful is when you start passing type constructors as template arguments - that is, instead of passing in a type as a template argument, you pass in a function that operates on types. Within the body of the template are calls to this function, which appear in the same places that template arguments would appear. So for example I could declare a template that takes a parameter R which is a type constructor, and in the body of the template I might declare a method whose return type is "R(String)". What "R(String)" evaluates to depends on what the value of "R" is when you instantiate the template. Some examples of R could be a constant [R(X) => int], the identity function [R(X) => X] or a type derived from the argument [R(X) => List[X]].</div>
<div>
<br /></div>
<div>
The example that they give in the paper is a visitor pattern - that is, you have a tree representing expression nodes, and you have two different visitors - one which evaluates the expression, and one which prints the expression as a string. In the former case, each visitor method returns a type appropriate to the evaluation - int, float, bool, etc. In the second case, the visitor methods all return type String. Because the visitor methods are all defined in terms of type constructors, you can use the same generic tree-walking code to handle both cases.</div>
<div>
<br /></div>
<div>
Well, that's all very neat, but...I wonder. It doesn't actually seem all that useful to me, or at least it doesn't seem all that useful to the average Joe Programmer (JP). You see, these type constructors don't work on normal classes of the kind JP would write, but only on templates that have these constructor calls built into them. Writing a class which takes advantage of type constructors presupposes that you have a certain kind of generality in mind. That is, given a particular data structure or algorithm, there are many dimensions along which we can generalize - you can think of a particular bit of code as being defined by some set of design criteria, and in generalizing the code we're taking some of those design criteria that are constants and replacing them with variables. We can't replace the entire thing with variables, because then we have no specification - our design becomes "do anything with anything".</div>
<div>
<br /></div>
<div>
The most common kind of generalization we see in practice is to interpolate between two specific use cases - that is, we enlarge the design just enough to encompass the two cases. If additional use cases come along, they may or may not fall within the envelope of what the design can support. (That's why I generally like to see at least three use cases before generalizing a particular design.)</div>
<div>
<br /></div>
<div>
This is exactly what they have done in the paper - their two use cases are "visitor that supports evaluation" and "visitor that supports converting into a string representation".</div>
<div>
<br /></div>
<div>
The thing is, though, is that this problem isn't a "real" problem in the sense that it's not a very hard problem to solve - there are many ways of coding those two use cases, and while some of the possible solutions are a little more verbose, they don't require super-advanced type theory either. The authors are deliberately avoiding any kind of dynamic typing because they trying to use the type system to prove that their code is correct, but I'm not convinced that their code is easier to *reason about* than an equivalent dynamic-typed solution would be. And to my mind, making it easier to think about what the code does is really the key to better programmer productivity.</div>
<div>
<br /></div>
<div>
I'm also not convinced that the kind of generality that they offer is the kind that most programmers would need. That is, a programmer who has a need for a "generic visitor" would be very likely, in my estimation, to need a visitor that is generalized in a way that the authors haven't thought of, and which would not be supported by their system.</div>
<div>
<br /></div>
<div>
To give an example, there's another kind of generality that is used daily by many Java and Python programmers, and which is much more useful. I'm going to call this "algorithmically-produced implementations". That is, given some ordinary abstract interface X that defines a set of methods, generate all of the method bodies using some rule. An example of this is mock objects for unit testing - you "mock out" the interface by generating methods that capture the parameter values and record them in a log.</div>
<div>
<br /></div>
<div>
In other words, rather than having functions that operate on *types*, we have essentially functions that operate on *methods* - given a type signature, return a method body. One could imagine a syntax for this, where '_' is taken to mean "anytime someone attempts to call a method that is undefined, call this method instead".</div>
<div>
<br /></div>
<div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace;"> def _[%RetType, %ArgTypes...](args:ArgTypes) -> RetType {</span></div>
<div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace;"> record(args);</span></div>
<div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace;"> return defaultValue[RetType]();</span></div>
<div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace;"> }</span></div>
<div>
<br /></div>
<div>
Of course, the language has to support "perfect forwarding" in order for this to work, but let's assume that it does indeed do so. (Note that the ... in the template argument list indicates that ArgTypes is a variadic template parameter - this allows the function to accept a variable number of arguments.)</div>
<div>
<br /></div>
<div>
Note that from an implementation standpoint, there are two ways that this can work. Approach #1 is to have the compiler replicate the body of "_" for each missing method. Approach #2 is to only have one instance of "_", but for each missing method the compiler generates a trampoline function that packs up the arguments into an array and calls "_". Which method will be used in Tart is something that I still have not decided.</div>
<div>
<br /></div>
<div>
In any case, the beauty of mock objects is that they work with almost any interface - you typically don't have to have mocking in mind when you design your interface, although there are occasionally times when you need to do so. And it's something that the average programmer can immediately grasp.</div>
<div>
<br /></div>
</div>
</div>
Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-19862677505774254932011-09-04T12:34:00.000-07:002011-09-04T12:35:11.416-07:00I/O Library is checked inWell, better late than never... <div><br></div><div>There are now low-level classes for reading/writing to files, standard in/out, and to memory. There are also reader classes for reading and writing text:</div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"> <div><font class="Apple-style-span" face="'courier new', monospace">tart.io.Console</font></div><div><font class="Apple-style-span" face="'courier new', monospace">tart.io.FileStream</font></div><div><font class="Apple-style-span" face="'courier new', monospace">tart.io.MemoryStream</font></div> <div><font class="Apple-style-span" face="'courier new', monospace">tart.io.StreamTextReader</font></div><div><font class="Apple-style-span" face="'courier new', monospace">tart.io.StreamTextWriter</font></div> <div><br></div></blockquote><div>...plus a host of unit tests to go along with them. I don't yet have "convenience methods" for opening text files, so for now the easiest way to read from a file is:</div><div> <br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">let reader = StreamTextReader(FileStream(filename))</font></div> <div><font class="Apple-style-span" face="'courier new', monospace">for line in reader {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> // do something with 'line'.</font></div> <div><font class="Apple-style-span" face="'courier new', monospace">}</font></div><div><font class="Apple-style-span" face="'courier new', monospace">reader.close();</font></div></blockquote><div><font class="Apple-style-span" face="'courier new', monospace"><br> </font></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-34932531967509479422011-08-31T01:05:00.001-07:002011-08-31T01:05:46.867-07:00MutabilityI've been reading up on the D language's idea of immutability. It makes some interesting choices, but I'm not certain they are the right choices for me. <div><br></div><div>D has two keywords, 'const' and 'immutable'. 'const' says that you can't modify the value, but someone else might. 'immutable' is a guarantee that the item will never be modified, and this guarantee may be backed up by storing the item in a protected memory page.</div> <div><br></div><div>Moreover, both 'const' and 'immutable' are transitive - that is, any data structure that is reachable by a const type is also const. So if you have a pointer inside a const struct, the thing it points to is automatically const as well.</div> <div><br></div><div>Another design point is that you can't typecast an immutable value to either const or mutable, since that would violate the guarantee of immutability. (Actually, I think there's a way you can, but attempting the mutate the value afterward may throw an exception if the value is in protected memory.)</div> <div><br></div><div>I like the distinction between const and immutable, however I tend to favor the formulation used in the JodaTime libraries: You have a base type which is 'readable', with two subtypes, mutable and immutable. So for example, you have "ReadableDate" which only defines accessors for reading the value, but does not guarantee that those values will not change; Then there is ImmutableDate, which adds no new methods but does guarantee immutability, and then MutableDate, which adds the accessors for mutating the value.</div> <div><br></div><div>The only problem with JodaTime is the extra work involved in writing 3 classes to represent the same concept. This is where C/C++/D gets it right, I think: You write the class once, with methods to both read and mutate the fields, and then you use a modifier keyword as a type constructor, which transforms the fully functional type into a more restricted version of that type.</div> <div><br></div><div>If we combine these two ideas together, we get something that works like this: 'immutable(Foo)' takes the type 'Foo' and subtracts from its definition all of the mutation methods. 'readable(Foo)' does the same, except that you can cast either a Foo or an immutable(Foo) into a readable(Foo), but not vice versa.</div> <div><br></div><div>How is the compiler to know which methods are mutation methods? Well, we have to tell it - this is one case where the compiler can't infer things automatically (As a general rule, Tart does not allow the compiler to infer an interface from its implementation. I realize that there are some languages which do exactly this, but I think that interfaces should be explicit.) Fortunately, we don't need to distinguish between readable and immutable in this case - all the compiler cares about is whether the method can mutate the state of the object or not. The main challenge here is to come up with a syntax that's easy to type, since approximately 25-50% of all instance methods will want to have this property.</div> <div><br></div><div>You also need a way for some fields to be mutable even on a readonly object. A typical example of this is reference counting: You want the object to appear to be immutable to the outside world, but internally you are changing the reference count. In C++ we accomplish this by declaring the data member as explicitly mutable, or by declaring the method itself as mutable. The latter can be accomplished better, I think, by allowing the method to cast 'self': So we'd say something like "let mself = mutable(self)", and then use mself to access the various fields.<br> <br></div><div>Finally, there's the question of transitivity. Tart already has a mechanism for defining non-transitive immutable member fields via the 'let' keyword instead. At the same time, I can't help feeling that the D rule is too aggressively transitive. I think that having an immutable array of pointers to mutable objects would be a fairly common use case.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-70560325124549558522011-08-29T14:24:00.000-07:002011-08-29T14:25:14.758-07:00The Copyable protocolOne of Tart's fundamental design decisions is that there should be no collection classes that have special, "privileged" status. In most programming languages, there are a few types that are built in to the compiler, and which have special syntactic sugar - so for example, in Java, arrays are a built-in type, and only arrays can use the bracket notation (array[n]) to access their elements. Whereas in Tart, the Array type is written in Tart, and moreover, any collection class can define an element access operator.<div> <br></div><div>Actually, this design principle represents an unrealizable ideal more than it does an actuality. In truth, arrays do have special status in two ways: array literals, and functions taking a variable number of arguments. Both of these cases cause the compiler to generate code that constructs a new array instance. But once constructed, an array is no more "special" than any other collection.</div> <div><br></div><div>There's a downside to this design principle, however. It's fairly common in programming to want to convert from one collection type to another - for example "flattening" a deque into an array, or converting a map into a list of tuples. In cases like these, it's highly inefficient to transfer the items one at a time from the source collection to the target collection. It would be better if there was some way to transfer elements en masse. Unfortunately, doing so requires knowing a lot about the internal representation of the collections involved.</div> <div><br></div><div>For example, many collection classes use arrays internally - ArrayList and Deque being two prime examples. If we could arrange a bulk transfer of elements from one array to another, much of the overhead of copying could be eliminated. However, those arrays are private - allowing code outside of the class access to those arrays would destroy the data-hiding abstraction of the container.</div> <div><br></div><div>This is where it's useful to have the compiler have special knowledge of some collections - because the compiler can recognize cases where a bulk transfer would be appropriate and generate code for it. But what if we wanted to extend this ability to user-created collection types? What we'd have to do is abstract the bulk transfer operation itself, so that the user-created classes could participate in bulk-transfer operations.</div> <div><br></div><div>The Copyable interface represents one approach to solving this problem. Users never use Copyable objects directly - instead, when you pass one collection to another - such as ArrayList.appendAll(collection) - the destination collection checks to see if the source collection supports the Copyable interface. If it does, then it initiates one or more bulk transfers from the source collection. If it does not, then it will transfer the elements the conventional way, one at a time.</div> <div><br></div><div>The Copyable interface makes certain assumptions about the destination container: It assumes that for a collection of size N, elements are numbered 0 .. N-1, and that sub-ranges of this numbering can be mapped onto ranges of contiguous addresses. So for example, elements 0-255 might be stored in one array, 256-511 stored in a second array, and so forth. Each bulk transfer operation specifies one of these contiguous sub-ranges as a destination buffer. It's up to the source collection to decide how to map it's own internal representation onto that buffer, and to copy its elements into that buffer. The source collection may have it's own internal divisions, which may be different from the destination's - in which case, the source collection may have to do more than one array copy to fill the destination buffer.</div> <div><br></div><div>The actual copying of data is typically done via Array.copyElements or Memory.copy, both which use memcpy to do the actual transfer. (Tart does not allow redefining the meaning of assignment, so all objects are treated as POD. The reason is that the garbage collector can move objects around, so any assumptions made by an overloaded assignment operator would be violated anyway. But with garbage collection, there's far less need to overload assignment anyway.)</div> <div><br></div><div>The copy operation is also synchronous - both source and destination are allowed to move things around in-between copy operations. There is no promise that the destination buffer will continue to exist after the copy finishes.</div> <div><div><br class="Apple-interchange-newline">BTW, the idea of Copyable was inspired and greatly influenced by the Python buffer protocol, although Copyable is a much smaller and less featureful concept.</div></div><div> <br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-22434100730721660952011-08-29T12:59:00.000-07:002011-08-29T13:00:15.944-07:00I/O LibraryI've taken Guido's advice about using file descriptors rather than FILE * handles, and as a result the i/o classes are coming along nicely. MemoryStream and StreamTextWriter are done, with unit tests. FileStream and StreamTextReader are written but still need tests. The character codecs got an overhaul as well.<div> <br></div><div>One of the nice things about all of this is that it has given me a chance to write lots of Tart code, which is a welcome break from writing the compiler in C++. You can definitely see the power of Tart when you have unit tests that look like this:</div> <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">stream.write([1, 2, 3, 4, 5]);</font></div> <div><font class="Apple-style-span" face="'courier new', monospace">assertContentsInOrder(stream.data, 1, 2, 3, 4, 5);</font></div></blockquote><br><div>In this case, 'stream' is a MemoryStream, and the 'write' method takes in an array of bytes, which in this case is an array literal. "stream.data" returns a reference to the underlying collection (an ArrayList). "assertContentsInOrder()" takes a collection and a variable number of elements, and asserts that the contents of the collection equals that list (it does this by calling iterators.equal()).</div> <div><br></div><div>This style of coding feels very Pythonic to me, yet it's all statically typed.</div><div><br></div><div>One minor disadvantage of using unix file descriptors is that there's no equivalent of feof(). The only way to know that you're at the end of file is to attempt to read, and then get 0 back as the result. This doesn't play so well with higher-level APIs, which are typically designed such that you can test for end of file before doing an actual read. fread() and its ilk provide this capability by reading ahead.</div> <div><br></div><div>This means that my lower-level i/o classes have to expose this same behavior - I can't define an "eof" predicate for class IOStream. Such a method would be expensive without buffering or read-ahead of some type. And since we want the IOStream interface to be platform-agnostic, that means that we can't define an eof method even on platforms which do support it for low-level streams. We have to go with the lowest-common-denominator (both of platforms and stream types), which means that all IOStreams have to have unix-style end-of-file behavior.</div> <div><br></div><div>Obviously the higher-level classes such as TextReader / TextWriter are buffered, so we can define an eof() method on all of these. It's only the lower-level unbuffered classes that don't support it.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-83727468553253016622011-08-19T13:15:00.000-07:002011-08-19T13:16:10.241-07:00Brainstorm: ScopedObject and PinnedScopedObject and Pinned are two features of Tart which are on my long-term TODO list.<div><br></div><div>ScopedObject is an interface that is used in conjunction with the 'with' statement. It has two methods: enterScope() and exitScope(). You'd use it like this:</div> <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">with mutex.locked() {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> // Mutex is locked while in this block, will be unlocked on exit.</font></div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace">with file = FileReader.open("foo.txt") {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> // File will be automatically closed on exit.</font></div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div> </blockquote><div><br></div><div>tart.gc.Pinned is a helper class for creating 'pinned' objects - that is, objects that are fixed at a given address and cannot be moved around by the garbage collector. Pinned objects aren't something that normal users of Tart would ever deal with - they are mainly useful for people who are implementing i/o libraries.</div> <div><br></div><div>Here's a typical example of how pinning would be used:</div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">def writeData(data:ubyte[]) -> int {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> with pinnedData = GC.pin(buffer) {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> with GC.unlocked() {</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> return lowLevelStream.writeData(pinnedData.get());</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div> <div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace">}</font></div></blockquote><div><br></div><div>Here's what this is doing: GC.pin() takes an object reference and returns a 'pinned' version of that object. Depending on what memory region the object lives in, the return value may be the original object with the 'pinned' bit set in the object header, or it may be a shallow clone of the object. Cloning generally will occur if the original object lives in a compacting collection space - the clone will be put into a different space where object addresses are stable.</div> <div><br></div><div>Note that the writeData() function will throw an exception if the buffer isn't pinned.</div><div><br></div><div>At the end of the outer with statement, the pinned object is disposed. In some cases, the data in the pinned object may get copied back to the original buffer. (Probably 'pin' will take some flags indicating whether the clone will be read/write or just read only.)</div> <div><br></div><div>The inner 'with' statement handles interactions between the garbage collector and blocking i/o. The 'unlocked' method tells the garbage collector that it's OK for collections to take place while we are waiting for the i/o to finish. At the end of the block, the garbage collector is locked again (meaning that collections can only take place when we tell it that it is safe to do so.) Within the 'unlocked' state, objects may move around in memory - which is why we had to make sure that the input buffer was pinned.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-91510163347218687802011-08-09T10:45:00.001-07:002011-08-09T10:45:25.652-07:00Fun with debug macrosI recently introduced some new macros for doing assertions and conditional tracing, which was inspired by a conversation on llvm-dev. Here's how the new macro is used: <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><font class="Apple-style-span" face="'courier new', monospace">DASSERT(super != NULL) << "Expecting a non-null super class for type: " << type;</font></div> </blockquote><div><br></div><div>In other words, the assertion macro acts like a stream operator, allowing you to print a message that includes dynamic fields. There's also a DMSG(condition) macro which prints a message only if 'condition' is true.</div> <div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><font class="Apple-style-span" face="'courier new', monospace">DMSG(TRACE_CODEGEN) << "Adding a static root entry for: " << var;</font></div> </div></blockquote><div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div>One feature that DASSERT and DMSG have is that, like all good debugging macros, they impose no cost when disabled. This means that (a) no side effects occur if the condition is false, and (b) if the condition is both false and is a compile-time constant, the compiler should remove the message code entirely.</div> <div><br></div><div>How does this work? Well, the DMSG and DASSERT macros construct a stream object. In the case of DMSG it's a generic output stream. In the case of DASSERT, it's a subclass of stream which calls abort() in it's destructor. Because the stream is a temporary object, it gets destructed at the end of the statement, after all of the messages have been printed.</div> <div><br></div><div>Here's what DASSERT actually looks like:</div><div><meta charset="utf-8"><span class="Apple-style-span" style="border-collapse: collapse; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><table id="src_table_0" style="font-size: 12px; font-family: Monaco, 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Lucida Console', monospace; border-collapse: collapse; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <tbody style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_22" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <td class="source" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 4px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; white-space: pre-wrap; vertical-align: top; "> <span class="com" style="font-size: 12px; color: rgb(136, 0, 0); "> </span><blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> <font class="Apple-style-span" size="2"><span class="com" style="color: rgb(136, 0, 0); "><font class="Apple-style-span" face="'courier new', monospace">#define</font></span><font class="Apple-style-span" face="'courier new', monospace"><span class="pln" style="color: rgb(0, 0, 0); "> DASSERT</span><span class="pun" style="color: rgb(102, 102, 0); ">(</span><span class="pln" style="color: rgb(0, 0, 0); ">expression</span><span class="pun" style="color: rgb(102, 102, 0); ">)</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">\</span><span class="pln" style="color: rgb(0, 0, 0); "><br> </span></font></font></blockquote></td></tr><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_23" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <td class="source" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 4px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; white-space: pre-wrap; vertical-align: top; "> <blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'courier new', monospace" size="2"><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">(</span><span class="pln" style="color: rgb(0, 0, 0); ">expression</span><span class="pun" style="color: rgb(102, 102, 0); ">)</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">?</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">(</span><span class="kwd" style="color: rgb(0, 0, 136); ">void</span><span class="pun" style="color: rgb(102, 102, 0); ">)</span><span class="lit" style="color: rgb(0, 102, 102); ">0</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">:</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="typ" style="color: rgb(102, 0, 102); ">Diagnostics</span><span class="pun" style="color: rgb(102, 102, 0); ">::</span><span class="typ" style="color: rgb(102, 0, 102); ">VoidResult</span><span class="pun" style="color: rgb(102, 102, 0); ">()</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">&</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">\</span></font></blockquote> </td></tr><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_24" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <td class="source" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 4px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; white-space: pre-wrap; vertical-align: top; "> <blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><font class="Apple-style-span" face="'courier new', monospace" size="2"><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="typ" style="color: rgb(102, 0, 102); ">Diagnostics</span><span class="pun" style="color: rgb(102, 102, 0); ">::</span><span class="typ" style="color: rgb(102, 0, 102); ">AssertionFailureStream</span><span class="pun" style="color: rgb(102, 102, 0); ">(</span><span class="com" style="color: rgb(136, 0, 0); ">#expression, __FILE__, __LINE__)</span></font></blockquote> </td></tr><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_25" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> </tr></tbody></table> </span></div><div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; ">Let's start with the last part. AssertionFailureStream is the stream object - it's the right-most token in the macro, so any stream operators (<<) that come after the macro will be applied to the stream.</span></div> <div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><br></span></div><div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; ">In the middle there's a C ternary operator '?:' which tests if 'expression' is true. </span><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; ">Because the precedence of the ternary operator is lower than <<, the stream operators will get applied to the stream object, rather than the expression as a whole. Also, C++ guarantees that only one of the two choices of a ternary operator will be evaluated, so this means that the stream object will not be constructed, nor will the stream operators be executed, if 'expression' is true.</span></div> <div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><br></span></div><div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; ">One catch is that both sides of a ternary expression have to be the same type - which in this case we want to be 'void'. Doing this requires another trick: pick some binary operator which has a lower precedence than << but higher than '?'. In this case, I've chosen the bitwise 'and' operator, '&'. Then create an overload for it which returns a void result:</span></div> <div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><br></span></div><div><span class="Apple-style-span" style="border-collapse: collapse; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; "><meta charset="utf-8"><table id="src_table_0" style="border-collapse: collapse; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <tbody style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_216" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <td class="source" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 4px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; white-space: pre-wrap; vertical-align: top; "> <blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><span class="com" style="color: rgb(136, 0, 0); "><font class="Apple-style-span" face="'courier new', monospace" size="2">/** Transforms a value of stream type into a void result. */</font></span></blockquote> </td></tr><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_217" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> <td class="source" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 4px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; white-space: pre-wrap; vertical-align: top; "> <blockquote class="webkit-indent-blockquote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial; border-color: initial; padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; "> <font class="Apple-style-span" face="'courier new', monospace" size="2"><span class="kwd" style="color: rgb(0, 0, 136); ">friend</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="kwd" style="color: rgb(0, 0, 136); ">void</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="kwd" style="color: rgb(0, 0, 136); ">operator</span><span class="pun" style="color: rgb(102, 102, 0); ">&(</span><span class="kwd" style="color: rgb(0, 0, 136); ">const</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="typ" style="color: rgb(102, 0, 102); ">VoidResult</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">&,</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="kwd" style="color: rgb(0, 0, 136); ">const</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="typ" style="color: rgb(102, 0, 102); ">FormatStream</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">&)</span><span class="pln" style="color: rgb(0, 0, 0); "> </span><span class="pun" style="color: rgb(102, 102, 0); ">{}</span></font></blockquote> </td></tr><tr id="sl_svn7f61ff0994496874093870ac41ad380f213ff38e_218" style="padding-top: 0px; padding-right: 0px; padding-bottom: 0px; padding-left: 0px; margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "> </tr></tbody></table><font class="Apple-style-span" face="Monaco, 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Lucida Console', monospace" style="font-size: 12px; "> </font></span></div><div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; ">'VoidResult is just an empty struct - it's just there to insure that our operator gets called. So 'VoidResult() & AssertionFailureStream(...)' now has type void.</span></div> <div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br></span></div><div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">One final thing needed to make this all work is to define appropriate stream operators for various compiler classes such as Variable and Type, which print out the object in human-readable form.</span></div> <div><span class="Apple-style-span" style="border-collapse: collapse; font-size: 12px; white-space: pre; -webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br></span></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-18548923332313642052011-08-09T09:47:00.000-07:002011-08-09T09:48:59.846-07:00Well, that was more work than I expected...It's been a while since I posted. Usually when I "go dark" for an extended period of time, it's either because (a) I'm feeling burned out from working on Tart and need an extended break, or (b) it's because I'm working on a massive changeset and I don't want to talk about it too much until it's submitted. This time it's (b).<div> <br></div><div>I've spent the last month or so updating Tart to work with the latest LLVM trunk. The LLVM APIs have changed significantly in preparation for the 3.0 release. The biggest change is that LLVM types now have first-class names, and types with different names are now distinct types even if they are structurally identical. In addition, the Opaque type is gone - instead you use a named struct with no body. (You can fill in the body later, or not.)</div> <div><br></div><div>The APIs have also changed - Types are no longer "const" (that is, the LLVM APIs will no longer produce or accept values of type 'const Type *'). This required a huge number of edits to my code.</div> <div><br></div><div>Also during this period I ran into several LLVM bugs in the new type system, and worked with the LLVM folks to diagnose and fix them. This includes a trip into DWARF hell, which is never fun.</div><div> <br></div><div>In any case, I've committed the changes so Tart is working again. Overall, I like the changes - for one thing, the generated IR is easier to read now that types have proper names. And with the ability to declare a type name with no body, I'll eventually be able to reduce the amount of work the compiler is doing, because I won't have to do a deep analysis on fields that are never dereferenced.</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com0tag:blogger.com,1999:blog-2813257058440983072.post-87695576965456348912011-07-17T16:56:00.000-07:002011-07-17T16:57:00.646-07:00When object orientation is the wrong answerOne of the major refactorings I did this week is to completely replace the implementation of the "isSubtype" test.<div><br></div><div>The "is subtype" test is a binary relation between two types. There's even an operator for it in Tart: "<:" which is the same one used by Scala. So the expression "A <: B" is true if A is either the same as B or is a subtype of B. This particular test gets called in a lot of places - for example, deciding which of two functions is a closer match involves doing subtype tests on all of the arguments.</div> <div><br></div><div>The way I originally implemented this in the compiler was by following the standard object-oriented approach: class Type, which is the base class of all types, has a pure virtual method "isSubtypeOf(const Type * base) const". Each subclass of Type (PrimitiveType, FunctionType, CompositeType, etc) overrides this and provides an implementation that is specific to that type.</div> <div><br></div><div>However, the subtype relation isn't quite as cut and dried as all that. For example, what if the type being tested is a type alias that points to some other type? Well, you have to dereference the alias before you can do the subtype test. OK so we do that. But now, what if the base type is also an alias? Well we have to dereference that too. So now every type has to know about aliases - either that, or every place that calls isSubtypeOf has to dereference the types first.</div> <div><br></div><div>It gets more complicated: What if the base type is a protocol? Any type can be a subtype of a protocol, because a protocol is simply a constraint - it says "this type has a method with such-and-such name and such-and-such signature". So for example, even primitive types have a "toString" method, which means that primitive types are technically considered subtypes of the "HasToString" protocol. OK so now every type has to know about protocols.</div> <div><br></div><div>What about ambiguous types? These are temporary types, created during the type inference pass, that represent a "cloud" of related types which haven't been fully resolved yet. So for example, if we call "min(a, b)" the return value might be an int, or a float, or even a String depending on which overload of "min" eventually gets chosen. Each ambiguous type has a generator which can iterate through all of the possible types, and that generator will return fewer and fewer results as we tighten up the constraints looking for a singular solution.</div> <div><br></div><div>The "isSubclassOf" test for ambiguous types requires that all of the "possible" types must each pass the subclass test, if any of them fails then the whole thing does.</div><div><br> </div><div>There are also "type assignments" such as "%T=int" - meaning that the type variable T is assigned the value "int" within the current environment. Now, what happens if you have a template instance, where one or more of the type parameters is a type assignment or some other funky type? For example: given that ArrayList[int] is a subtype of List[int], is ArrayList[%T=int] also subtype of List[int]? The answer is, it depends on the environment - so now isSubtypeOf() needs to know about environments.</div> <div><br></div><div>As you can imagine, with all these complexities the code is starting to look pretty nasty. Time for a redo.</div><div><br></div><div>In the new scheme, isSubtype(a, b) is now just a regular function - not even a class method. It's a fairly large function, since it has to handle all of the logic I've outlined above. However, it's not as large as you might think. Mainly what it does in complex cases is simplify the case by one step and then call itself recursively with the simplified arguments. Thus, if either of the two arguments are an ambiguous type, it generates the set of possibilities, and then calls itself for each possibility.</div> <div><br></div><div>The biggest benefit is that all of the logic for the subtype relation is all located in a single file, which is much easier to understand than having it scattered across two dozen source files. Although some types have different logic, there's a lot of commonality too - for example, there's a whole set of types which have no concept of inheritance of subtyping - booleans and machine address types are an example - they both handle the "isSubtype" test the same way - by delegating to "isEqual".</div> <div><br></div> Talinhttp://www.blogger.com/profile/11160561365552764247noreply@blogger.com1