It's been a crazy last couple of weeks. I started my new position as a linux driver developer on June 18th, followed shortly by the crazy Colorado Springs wild fire. But, once again, I get to dive deep into native programming and get better at exactly how the linux kernel works. Unfortunately, my C(++) skills have gotten rusty in the last 4 years or so.
It's not like I have written Zero C(++) programs, but they have been few and far inbetween. So the last few days while I've been at home, I've been re-reading Bruce Eckel's free book on C++. The reason I am reading this, as opposed to my old copy of C: The Complete Reference, is that A) I need to get better at C++ and B) Bruce Eckel's book basically compares and contrasts many of the differences between C and C++.
In regards to the 2nd aspect, I like that this book can essentially help me kill two birds with one stone. It highlights many of the untyped features/pitfalls of the C language, and what C++ does to overcome them. But by covering how C would do something, and then contrasting it with the C++ way, it's kind of like getting a refresher on C while learning C++. Because of this, it is recommended that you know the fundamentals of C before reading Bruce Eckel's book. I still highly recommend this book because it's one of the few books that actually talks about header files, what inclusion guards are, and at least a brief look at how and what linking object files is for. Bruce also wrote a 2nd volume for C++, and it includes are more thorough examination of some advanced topics in C++ (eg, templates and the STL). I also bought some notes from Scott Meyer's on C++11x since I think if I am going to write in C++, it may as well be the newest version with some of the included goodies.
As to the first point listed above, I need to get better at C++ because LLVM is written in C++. I have been somewhat concerned to learn that the lead programmer (and probably others) for the LLVM project is paid by Apple, and thus the Mac is getting all the love (for example, LLDB only works on Mac OS X, and libc++ likewise is OS X only). I have no love for Apple (flame me all you want, but their tyrannical control is almost the worst of any big company I know of, but as the article I linked to indicates, this is because I am all for freedom, even if that freedom requires a learning curve). I find it ironic that in this country that is supposed to love freedom so much, we are willing to give up so much of it to corporations who dictate to us how things will be or makes it "just work" even if making it just work takes away my freedoms. If you are going to argue that the "free market" handles this by letting the consumer decide to choose the company they want, tell that to all the litigation happy companies that use absurd patents to enforce their way of doing things.
But, I will stick with LLVM for Shi, since it is still an open source project. Yes, I am still working on it, albeit very slowly. I'm currently alternating between 3 books now, a book on compiler design, the SICP book, and a book on comparative programming languages. Not to mention getting back up to speed on the linux kernel, and familiarizing myself with Gambit scheme. Right now though, I am focusing on lexical analysis, or the ability to discern tokens from a text stream. I decided to go full on with C++ for the lexer, so I've also been looking at using Boost's Regex library to help me do this. The little tutorial that the LLVM project gives is just way too trivial, so I'm just going to plow through the Basics of Compiler Design book.
Fortunately, the r7rs draft already has a pseudo context free grammar, so that will help me figure out what to tokenize. Of course, shi isn't going to be r7rs compliant...I just want to use that as a starting point. I intend shi to be more grammatically similar to clojure actually, as I find that syntax easier to read than scheme. I also like the type hints (annotations) from clojure better. But of course, the biggest thing for me is going to be the ability to generate native code on the fly via LLVM/clang, so that I can call libraries dynamically and without having to do any weird data marshalling (my thought is the ability to essentially #include header files...which is one of the reasons I am looking at gambit scheme right now, to see how they compile scheme code to C code).
Tuesday, July 10, 2012
Friday, May 11, 2012
EBNF and lexer time
So, what's the first step in making a language? Honestly, I don't know :) I'm kind of winging this as I go. But the starting point seems to be:
1) Decide on your features
2) Decide on your grammar
3) Make an EBNF to describe the language
4) Create a lexer
5) Create a syntax parser
6) Create a compiler/interpreter/VM
I have a rough feature set in place, so I think the next logical step will be to create the CFG and/or EBNF that describes the grammar. What's a CFG and EBNF? A CFG is a context free grammar. I can't go into too much detail, but if you pick up a book on formal languages, it should decribe what these are. The EBNF is the Enhanced Backus Naur Form which is a recursive description of the structure of a language. Given an EBNF, there are parser generators like ANTLR or BISON which can spit out parser generators for you.
But let me step back a moment. What is the difference between lexer and a parser? And what is a lexer anyway? One of the first things that a compiler or interpreter must do is recognize the tokens in a string. In fact, lexers and tokenizers are synonymous basically. A token is a discrete lexical unit (see why the two are the same?). Take for example this sentence. The words "Take", "for", "example", "this", and "sentence" would all be tokens. Does white space always delineate tokens? Not necessarily. And often, things other than white space can delineate tokens. Take this example:
int i = 2+3;
What are the tokens? [ int, i, =, 2, +, 3, ;]. But notice that no white space separates 2+3, and yet those are 3 separate tokens. This is why you need a lexer, and ideally you need a lexer generator like YACC. But how do you make a lexer? If you have used regular expressions before, this kind of looks like a regex doesn't it? But how do regexes work? Fundamentally, a regular expression defines a "regular" language (a language is regular because a regular expression can be written to recognize all strings producible by that language). In turn, regular expressions can be converted into NFAs (non-deterministic finite automata) which in turn can be converted into DFAs (deterministic finite automata).
If you are curious about regular languages, regular expressions, NFAs, DFAs, pushdown finite automatas and context free grammars, then I recommend you pick up a good book on Automata Theory. People familiar with finite state machines and graph theory really won't have any problem picking up on automata theory. To extremely oversimplify things, an NFA has states, one of which is a starting state, and one or more states (including possibly the start state) is an accepting state. States can be transitioned to by "consuming" an element in the string, or possibly not consuming anything at all (the epsilon transition). The "consumption" of the characters in the string leads you to a state, and once the string is fully consumed, either you are in an accepting state or not (or possibly a character in the string has no transition, in which case it's an unrecognized string). They are called non-deterministic, because each vertex (or state) can have more than one possible transition. A DFA on the other hand can only have one possible transition per state. So from a graph point of view, in a DFA, you have a directed graph with only one outgoing edge per vertex (but possibly many incoming edges).
Ok, so that's all well and good...but how do you actually PROGRAM one. Well, that's what I intend on doing :) In the next few blogs, I'll put up some of the code that actually performs the lexing for a scheme like grammar. Originally, I had thought about writing this in scheme, but since LLVM is written in C++, I might do it in C++ instead. But, I'll probably eventually do this in scheme anyway, just to get some practice with it. I'll also intersperse this with the beginnings of an EBNF for Shi. It seems to me like the EBNF is really the first thing I should be doing, as it will contain valid tokens that the lexer has to recognize.
1) Decide on your features
2) Decide on your grammar
3) Make an EBNF to describe the language
4) Create a lexer
5) Create a syntax parser
6) Create a compiler/interpreter/VM
I have a rough feature set in place, so I think the next logical step will be to create the CFG and/or EBNF that describes the grammar. What's a CFG and EBNF? A CFG is a context free grammar. I can't go into too much detail, but if you pick up a book on formal languages, it should decribe what these are. The EBNF is the Enhanced Backus Naur Form which is a recursive description of the structure of a language. Given an EBNF, there are parser generators like ANTLR or BISON which can spit out parser generators for you.
But let me step back a moment. What is the difference between lexer and a parser? And what is a lexer anyway? One of the first things that a compiler or interpreter must do is recognize the tokens in a string. In fact, lexers and tokenizers are synonymous basically. A token is a discrete lexical unit (see why the two are the same?). Take for example this sentence. The words "Take", "for", "example", "this", and "sentence" would all be tokens. Does white space always delineate tokens? Not necessarily. And often, things other than white space can delineate tokens. Take this example:
int i = 2+3;
What are the tokens? [ int, i, =, 2, +, 3, ;]. But notice that no white space separates 2+3, and yet those are 3 separate tokens. This is why you need a lexer, and ideally you need a lexer generator like YACC. But how do you make a lexer? If you have used regular expressions before, this kind of looks like a regex doesn't it? But how do regexes work? Fundamentally, a regular expression defines a "regular" language (a language is regular because a regular expression can be written to recognize all strings producible by that language). In turn, regular expressions can be converted into NFAs (non-deterministic finite automata) which in turn can be converted into DFAs (deterministic finite automata).
If you are curious about regular languages, regular expressions, NFAs, DFAs, pushdown finite automatas and context free grammars, then I recommend you pick up a good book on Automata Theory. People familiar with finite state machines and graph theory really won't have any problem picking up on automata theory. To extremely oversimplify things, an NFA has states, one of which is a starting state, and one or more states (including possibly the start state) is an accepting state. States can be transitioned to by "consuming" an element in the string, or possibly not consuming anything at all (the epsilon transition). The "consumption" of the characters in the string leads you to a state, and once the string is fully consumed, either you are in an accepting state or not (or possibly a character in the string has no transition, in which case it's an unrecognized string). They are called non-deterministic, because each vertex (or state) can have more than one possible transition. A DFA on the other hand can only have one possible transition per state. So from a graph point of view, in a DFA, you have a directed graph with only one outgoing edge per vertex (but possibly many incoming edges).
Ok, so that's all well and good...but how do you actually PROGRAM one. Well, that's what I intend on doing :) In the next few blogs, I'll put up some of the code that actually performs the lexing for a scheme like grammar. Originally, I had thought about writing this in scheme, but since LLVM is written in C++, I might do it in C++ instead. But, I'll probably eventually do this in scheme anyway, just to get some practice with it. I'll also intersperse this with the beginnings of an EBNF for Shi. It seems to me like the EBNF is really the first thing I should be doing, as it will contain valid tokens that the lexer has to recognize.
I'm a developer again
It's official: in the next few weeks, I'll be doing linux driver development at my company. I hope I can bring some of my testing experience into this position, and having had this experience, I can definitely say that all developers should have a testing background, and all testers should have a development background.
While reading some scheme paper (I can't recall which one), there was a quote by Richard Feynman where he said, "What I cannot build, I do not understand". I think this is really something that has to be understood. It is in fact why I studied Computer Science and not Electrical Engineering. A long time ago I read a saying describing, in a nutshell, the difference between scientists and engineers: "Scientists build in order to learn. Engineers learn in order to build". By that criterion, I am most definitely a scientist. I want to build things so that I understand them. My end goal is not actually whatever I built, but what I learned.
So getting back into driver development will help me understand better how operating systems work. Creating my own language will help me better understand the theory of computation. Implementation is, in my eyes, a necessary evil; a means to an end, but not the end itself. Without rolling up your sleeves and getting your hands dirty, you won't really understand something.
This is also the key to Buddhism. People are often surprised when I tell them Buddhism is not a religion or a philosophy. To the western mind, this doesn't seem possible. So people ask me if Buddhism eschews beliefs, is not a religion, and also distrusts concepts ( and is thus not a philosophy) what could Buddhism possibly be? When I say that a true Buddhist is a mystic, most are truly confused. What is a mystic you ask? A mystic trusts only his experience and awareness.
A Buddhist doesn't ruminate, or contemplate. The only way to "know" is to be aware. It is the acting of "being", and simply being conscious of this moment. The only way to "know" life is to 100% fully be in it. One doesn't "get" life by simply regurgitating what prior masters said. The only way to know life is to roll up your sleeves and live it. It is not to be gained through mental fortitude, nor steadfast belief. This is no different than saying one "knows" math by reading a book on it.
So although I am nervous about dealing with customers again (that's definitely one nice thing about being in Test, we don't deal with clients directly), this is really something I needed to do. I am looking forward to digging deeper, and being able to say, "what I have built, I understand".
While reading some scheme paper (I can't recall which one), there was a quote by Richard Feynman where he said, "What I cannot build, I do not understand". I think this is really something that has to be understood. It is in fact why I studied Computer Science and not Electrical Engineering. A long time ago I read a saying describing, in a nutshell, the difference between scientists and engineers: "Scientists build in order to learn. Engineers learn in order to build". By that criterion, I am most definitely a scientist. I want to build things so that I understand them. My end goal is not actually whatever I built, but what I learned.
So getting back into driver development will help me understand better how operating systems work. Creating my own language will help me better understand the theory of computation. Implementation is, in my eyes, a necessary evil; a means to an end, but not the end itself. Without rolling up your sleeves and getting your hands dirty, you won't really understand something.
This is also the key to Buddhism. People are often surprised when I tell them Buddhism is not a religion or a philosophy. To the western mind, this doesn't seem possible. So people ask me if Buddhism eschews beliefs, is not a religion, and also distrusts concepts ( and is thus not a philosophy) what could Buddhism possibly be? When I say that a true Buddhist is a mystic, most are truly confused. What is a mystic you ask? A mystic trusts only his experience and awareness.
A Buddhist doesn't ruminate, or contemplate. The only way to "know" is to be aware. It is the acting of "being", and simply being conscious of this moment. The only way to "know" life is to 100% fully be in it. One doesn't "get" life by simply regurgitating what prior masters said. The only way to know life is to roll up your sleeves and live it. It is not to be gained through mental fortitude, nor steadfast belief. This is no different than saying one "knows" math by reading a book on it.
So although I am nervous about dealing with customers again (that's definitely one nice thing about being in Test, we don't deal with clients directly), this is really something I needed to do. I am looking forward to digging deeper, and being able to say, "what I have built, I understand".
Saturday, May 5, 2012
How do you make a language? Good question...
So here I am, trying to figure out how to make my own scheme-like language, but I am not really sure where to start. I actually never took compiler theory in school, but Automata Theory was a required class. But even though I did take automata theory, that was many moons ago, and I have since forgotten a lot about it. I mean, what DOES it take to create a language anyway?
How much do I need to know about lexers and tokenizers? Does my language have to be understood by a LALR parser? An LL parser? And how do I make a parser anyway? Do I have to use something like YACC and Bison, or maybe ANTLR? What about my EBNF forms, how do I know they are complete? Does the language have to be a context free grammar? What does context free mean anyway? Is a context free language different from a regular language?
And these are really more just grammar production and syntax questions. What about creating control forms, concurrency support, tail-call optimization, etc etc that are features of the language? Where does one even begin when trying to design a language?
That's why I've decided to look at the R6RS scheme reference as a starting point. This language (which I am thinking of calling Shi, is the Chinese transliteration for the Pali word Vijnana which very loosely translates to "mind") won't actually be a scheme per se, but it will be scheme-like, just as clojure isn't exactly a lisp or scheme (however, the more I learn about scheme, the more clojure seems like a scheme, since it is a lisp-1 and it is more functional in nature).
However, that will only get me so far. For example, what other features in the language need to be implemented? What exactly is the goal of this language? So I decided to list down some of the things I wanted to implement:
- Persistent data structures
- Lazy evaluation by default
- Dynamically typed by default, but with type hints
- Tail call optimized
- JIT'ed
- Support for continuation passing style
- Support for C FFI
- Some kind of concurrency support (debating between STM and message passing)
- Garbage collected
- lisp1 style lexically scoped with one namespace
- Hygienic macros only
Some features I'd eventually like to implement (but probably in libraries)
And that's for starters. The design decisions above will impact the implementation. From what I've read about LLVM so far, it looks like the LLVM IR will give me support for #5, #7 and #9 above. It will also provide #4, but only on x86(_64) and PowerPC (but not the ARM...dammit). #3 will be interesting, I'll have to think about how to do this (I'll probably peek at the Clojure source code, and see how they do this, as I think it's a pretty cool feature). The immutable data structures will have to be provided at a somewhat higher level. Although LLVM provides primitives for immutability, this is different from actually implementing persistent data structures. Often, red-black trees are used to create associative arrays for example, but I still have to figure out how to make the structure persistent.
Even just figuring out what goes into making a programming language has been pretty fascinating so far, and I have only scratched the surface. Ultimately, what fascinates me is the theory of computation itself, and I hope that creating my own language based on scheme will give me a greater insight into the lambda calculus and computation itself.
Even just figuring out what goes into making a programming language has been pretty fascinating so far, and I have only scratched the surface. Ultimately, what fascinates me is the theory of computation itself, and I hope that creating my own language based on scheme will give me a greater insight into the lambda calculus and computation itself.
How does scheme do tail call optimization?
Last night, I was curious how to implement tail-call optimization for Shi (the language I am going to work on). I was curious how current scheme implementations did this. Since many schemes are implemented in C how do you do tail call optimization if C itself doesn't do tail call optimization?
But first, what does TCO really do anyway? And why do so many C(++) programmers lambast functional style recursion? I have to laugh when FW engineers at my company poo-poo recursion. Unfortunately, engineers who are not familiar with other languages aren't even aware that it's not recursion that is at fault, but the lack of sophistication of the C(++) compiler.
The unenlightened think that all languages suffer stack overflows. This is not true however. In brief, when a function call is made, a stack frame is allocated on the call stack, and the call stack has a limited amount of memory. One of the duties of a stack frame is to provide a return address so that as one function call completes, the stack frame is popped off, and the program can return to where the execution was left off. So in recursion without TCO, a new stack frame is allocated for every function call, and this is why you can "blow the stack". This is one reason why C(++) programmers (claim) recursion is so bad. In truth, I think most imperative style language programmers simply don't want to wrap their brains around recursion (or if you think lazily, induction) . The other mythical reason imperative style programmers claim recursion is bad is because procedure calls are expensive (because you have to push a new frame onto the call stack). This too is erroneous.
They are myths, however they are correct from a C(++) point of view. But again, don't make the mistake that recursion or function calls themselves are bad which may dissuade open-minded programmers from attempting to learn functional style programming if they only listen to their unenlightened peers. For example, the D programming language DOES do tail call optimization. But how did these myths come about in the first place?
In one part of the important "Lambda Papers" by the legendary Guy Steele called somewhat verbosely, "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO", Steele explains why function calls are not expensive as believed. As the title somewhat indicates, this gives a historical account over how function calls got a bad rap in the first place and gives an interesting perspective on the attitudes towards GOTO (from way back in the day). I recommend people read this, as it is an interesting account. But germane to this discussion, Steele debunks why function calls are considered "expensive". Steele basically points out three things:
1) GOTO statements are "universal" control flow statements
2) GOTO's are cheap, because in machine code, they are just a branch or a jump (as opposed to a switch or a case for example which becomes many machine code ops
3) Procedure calls are in essence GOTOs that can pass in arguments
Given the above three, function calls are therefore "cheap" and also become control flow in their own right. Interestingly, the paper mentions that stack space does not have to be consumed when using this "GOTO" method for tail recursion when lexical scoping is used (as opposed to dynamic scoping as in lisp). I presume this is because when variables are lexically scoped, the stack frame itself carries the reference(s) to the variables, as opposed to having variables being passed around dynamically. I could be mistaken on this point though.
So, TCO makes it possible to not consume a stack frame on every function call. And although the paper hints at how to do this from an assembly point of view, that still didn't explain how schemes that use C as the Intermediate Represenation performs TCO, since C itself can't do TCO. At first, I thought maybe they used setjmp/longjmp to save off the stack frame, and then on the recursive call use longjmp to go back. The problem is the unwinding of the stack frames (which may point to no longer valid frames). Still, it seems at least possible to do it this way.
I then came across something called a "trampoline", which I recognized somewhat from Clojure. A trampoline in clojure can be used for mutual recursion, but the trampoline described here is a function which "jumps" to other functions. Also after reading this, I came across an abstract discussing how to use the heap to perform tail call recursions.
This is all pretty fascinating, and I wish I had read the lambda papers before. I am even starting to read the legendary SICP book so that I can better understand Scheme. I guess Clojure was kind of like the gateway drug into functional programming and lisps :) It's even made me look a little at haskell....but first, I want to get Shi rolling.
But first, what does TCO really do anyway? And why do so many C(++) programmers lambast functional style recursion? I have to laugh when FW engineers at my company poo-poo recursion. Unfortunately, engineers who are not familiar with other languages aren't even aware that it's not recursion that is at fault, but the lack of sophistication of the C(++) compiler.
The unenlightened think that all languages suffer stack overflows. This is not true however. In brief, when a function call is made, a stack frame is allocated on the call stack, and the call stack has a limited amount of memory. One of the duties of a stack frame is to provide a return address so that as one function call completes, the stack frame is popped off, and the program can return to where the execution was left off. So in recursion without TCO, a new stack frame is allocated for every function call, and this is why you can "blow the stack". This is one reason why C(++) programmers (claim) recursion is so bad. In truth, I think most imperative style language programmers simply don't want to wrap their brains around recursion (or if you think lazily, induction) . The other mythical reason imperative style programmers claim recursion is bad is because procedure calls are expensive (because you have to push a new frame onto the call stack). This too is erroneous.
They are myths, however they are correct from a C(++) point of view. But again, don't make the mistake that recursion or function calls themselves are bad which may dissuade open-minded programmers from attempting to learn functional style programming if they only listen to their unenlightened peers. For example, the D programming language DOES do tail call optimization. But how did these myths come about in the first place?
In one part of the important "Lambda Papers" by the legendary Guy Steele called somewhat verbosely, "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO", Steele explains why function calls are not expensive as believed. As the title somewhat indicates, this gives a historical account over how function calls got a bad rap in the first place and gives an interesting perspective on the attitudes towards GOTO (from way back in the day). I recommend people read this, as it is an interesting account. But germane to this discussion, Steele debunks why function calls are considered "expensive". Steele basically points out three things:
1) GOTO statements are "universal" control flow statements
2) GOTO's are cheap, because in machine code, they are just a branch or a jump (as opposed to a switch or a case for example which becomes many machine code ops
3) Procedure calls are in essence GOTOs that can pass in arguments
Given the above three, function calls are therefore "cheap" and also become control flow in their own right. Interestingly, the paper mentions that stack space does not have to be consumed when using this "GOTO" method for tail recursion when lexical scoping is used (as opposed to dynamic scoping as in lisp). I presume this is because when variables are lexically scoped, the stack frame itself carries the reference(s) to the variables, as opposed to having variables being passed around dynamically. I could be mistaken on this point though.
So, TCO makes it possible to not consume a stack frame on every function call. And although the paper hints at how to do this from an assembly point of view, that still didn't explain how schemes that use C as the Intermediate Represenation performs TCO, since C itself can't do TCO. At first, I thought maybe they used setjmp/longjmp to save off the stack frame, and then on the recursive call use longjmp to go back. The problem is the unwinding of the stack frames (which may point to no longer valid frames). Still, it seems at least possible to do it this way.
I then came across something called a "trampoline", which I recognized somewhat from Clojure. A trampoline in clojure can be used for mutual recursion, but the trampoline described here is a function which "jumps" to other functions. Also after reading this, I came across an abstract discussing how to use the heap to perform tail call recursions.
This is all pretty fascinating, and I wish I had read the lambda papers before. I am even starting to read the legendary SICP book so that I can better understand Scheme. I guess Clojure was kind of like the gateway drug into functional programming and lisps :) It's even made me look a little at haskell....but first, I want to get Shi rolling.
Monday, April 30, 2012
Making a Scheme...the grand plan
Man I hope I don't jinx myself, but there's a pretty good chance I might be working in a new position soon and I won't be an SDET anymore. Lest Mr. Murphy come and visit me, I won't say what I might be doing until all the i's are dotted, and all the t's crossed. But I will say that I will be doing a lot more low-level coding again.
So, it looks like once again, I'll be switching focus on what I'll be doing for my hobby time. I'll be getting knee deep into linux internals again and need to brush up on my C. I'm also going to spend a little more time looking at the Minix source code. But especially, I'll be looking at LLVM and Scheme, specifically PLT Racket. Why all of this? And isn't Scheme a higher level language?
Let me start with why I am looking at Scheme now. Although Clojure is a pretty cool language (especially the Software Transactional Memory, which I haven't seen an equivalent of in any other Lisps), it's still in Virtual Machine land. And unfortunately, Java isn't all that great at interfacing with low-level C shared libraries or OS API's. That's where Scheme comes in. There are a couple of flavors of Scheme out there that have the ability translate into C code (for example Gambit Scheme and Chicken Scheme). And although both of those Schemes look kind of cool, I am currently looking at PLT Racket (formerly known as PLT Scheme).
I'm even reading a bit of the R6RS standard, in order to help me wrap my head around Scheme a little better (Clojure, though a relative of lisp, seems to me to be neither truly a Common Lisp nor Scheme derivative...in essence, it seems to be its own branch on the lisp family tree along with language like Shen). Although python is nice, and it is pretty easy, I want to learn a new higher level language that will let me interface with C more easily. Scheme fits this bill, but it does have a drawback that I mentioned above....no easy concurrency support (and yeah, I have read that continuations can be used for a kind of parallelism, but I am not sure it can be used for concurrency).
So this is where LLVM fits in. LLVM is a set of libraries which provides a front end (convert source code to the AST), optimizer and code generator (to generate the actual binary machine code for a specific architecture) for a programming language. LLVM is an interesting project, as it aims to help people write compilers, interpreters, or even JIT/VM's. It can do so by providing a "universal" Interface Representation called the LLVM IR (I like to think of it as a universal assembly). One could even create a language (it has lexers, scanners and parsers as well) with it. And LLVM makes it trivial to call into the C ABI.
Do you see where I am heading with this?
R6RS Scheme standard
LLVM to create a JIT'ed language that can easily interface to C
There's one last piece of the puzzle...concurrency support. Right now, the rage seems to be Erlang style message passing (Actors) for concurrency, but STM is gaining a lot of traction (Scala is implementing not one, but three STM libraries, haskell has 2 STM implementations, and pypy is experimenting with STM support). I found a pretty interesting article by a C++ guru Bartosz Milewski on STM, including a link to an academic paper on Transactional Locking II.
Previously, I had toyed with the idea of implementing Clojure style syntax in D. But the more I think about it, I realized it failed to satisfy several goals:
1) The stable dmd compiler only supports x86. I want to work with ARM processors
2) The front end to dmd2 is not open source
3) The LLVM based compiler ldc is not stable for D and is lagging behind
4) While it would make adding support for D modules easy, my real goal is support for C libraries
5) I would have to master D syntax and lisp/scheme
So I decided to something even harder:
1) Learn LLVM, including garbage collection and JIT byte generation
2) Learn how to make a lisp reader (it will be a LLVM based app )
3) Figure out how to implement STM in all of this
4) Slowly add in R6RS requirements (but not all)
Yeah yeah...I only have so much hobby time. But creating a language is really something I've wanted to do for a LOOONG time. I am getting close to paying off all my debts, which means I will be able to go and start on my Master's degree fairly soon. And I really want to be able to design my own language. Yup, I know, it's a dream of a lot of people, but I still think it would be cool. But I also want it to be practical.
Some of the things that appealed to me about Clojure was that:
1) The syntax seemed easier for me to read that other lisps and schemes (more than just parens)
2) The appeal of built-in concurrent programming via STM
3) More scheme-like functional approach (immutability as the default for example)
4) Supports both a JIT bytecode generation, and a AOT compiled mode
So I definitely want to keep these in the toy language I will create. But of course, there's one big hole in Clojure...good C/C++ library support. Where Clojure can easily interface with Java, I want this language to easily interface with C (and ideally in both directions...but that might be too hard to support for now). As a consequence, I want the language to support both a JIT'ed and AOT compiled (native) mode.
This is obviously a monumental task. But I think it will force me to become a better Computer Scientist. I will have to get better at many of the fundamentals of CS. And yes, you DO need the things you learn about in school at work (choosing the right data structures, understanding complexity analysis to find poor algorithms, the ability to prove your solution is correct, etc etc). Moreover, I am a firm believer that having learned several languages, and more importantly, different styles of programming has made me a better programmer. When I was interviewing for my new position (at my own company), one of the interviewers noticed that I had Clojure down on my resume. He seemed impressed and curious at the same time (he had heard of Clojure, and did a tiny bit of elisp, but thought lisp was too hard).
My feeling is that all the naysayers of lambdas in the upcoming Java 8 will eventually see their usefulness, instead of just decrying them as a "me too" feature for Java to catch up with C# on the bullet point list. But, much to my surprise, many engineers are loathe to change. I guess that's just one reason I consider myself a scientist rather than an engineer (engineers after all want stability, but scientists, in their quest for truth must be willing to give up the old in order to learn the new).
So, it looks like once again, I'll be switching focus on what I'll be doing for my hobby time. I'll be getting knee deep into linux internals again and need to brush up on my C. I'm also going to spend a little more time looking at the Minix source code. But especially, I'll be looking at LLVM and Scheme, specifically PLT Racket. Why all of this? And isn't Scheme a higher level language?
Let me start with why I am looking at Scheme now. Although Clojure is a pretty cool language (especially the Software Transactional Memory, which I haven't seen an equivalent of in any other Lisps), it's still in Virtual Machine land. And unfortunately, Java isn't all that great at interfacing with low-level C shared libraries or OS API's. That's where Scheme comes in. There are a couple of flavors of Scheme out there that have the ability translate into C code (for example Gambit Scheme and Chicken Scheme). And although both of those Schemes look kind of cool, I am currently looking at PLT Racket (formerly known as PLT Scheme).
I'm even reading a bit of the R6RS standard, in order to help me wrap my head around Scheme a little better (Clojure, though a relative of lisp, seems to me to be neither truly a Common Lisp nor Scheme derivative...in essence, it seems to be its own branch on the lisp family tree along with language like Shen). Although python is nice, and it is pretty easy, I want to learn a new higher level language that will let me interface with C more easily. Scheme fits this bill, but it does have a drawback that I mentioned above....no easy concurrency support (and yeah, I have read that continuations can be used for a kind of parallelism, but I am not sure it can be used for concurrency).
So this is where LLVM fits in. LLVM is a set of libraries which provides a front end (convert source code to the AST), optimizer and code generator (to generate the actual binary machine code for a specific architecture) for a programming language. LLVM is an interesting project, as it aims to help people write compilers, interpreters, or even JIT/VM's. It can do so by providing a "universal" Interface Representation called the LLVM IR (I like to think of it as a universal assembly). One could even create a language (it has lexers, scanners and parsers as well) with it. And LLVM makes it trivial to call into the C ABI.
Do you see where I am heading with this?
R6RS Scheme standard
LLVM to create a JIT'ed language that can easily interface to C
There's one last piece of the puzzle...concurrency support. Right now, the rage seems to be Erlang style message passing (Actors) for concurrency, but STM is gaining a lot of traction (Scala is implementing not one, but three STM libraries, haskell has 2 STM implementations, and pypy is experimenting with STM support). I found a pretty interesting article by a C++ guru Bartosz Milewski on STM, including a link to an academic paper on Transactional Locking II.
Previously, I had toyed with the idea of implementing Clojure style syntax in D. But the more I think about it, I realized it failed to satisfy several goals:
1) The stable dmd compiler only supports x86. I want to work with ARM processors
2) The front end to dmd2 is not open source
3) The LLVM based compiler ldc is not stable for D and is lagging behind
4) While it would make adding support for D modules easy, my real goal is support for C libraries
5) I would have to master D syntax and lisp/scheme
So I decided to something even harder:
1) Learn LLVM, including garbage collection and JIT byte generation
2) Learn how to make a lisp reader (it will be a LLVM based app )
3) Figure out how to implement STM in all of this
4) Slowly add in R6RS requirements (but not all)
Yeah yeah...I only have so much hobby time. But creating a language is really something I've wanted to do for a LOOONG time. I am getting close to paying off all my debts, which means I will be able to go and start on my Master's degree fairly soon. And I really want to be able to design my own language. Yup, I know, it's a dream of a lot of people, but I still think it would be cool. But I also want it to be practical.
Some of the things that appealed to me about Clojure was that:
1) The syntax seemed easier for me to read that other lisps and schemes (more than just parens)
2) The appeal of built-in concurrent programming via STM
3) More scheme-like functional approach (immutability as the default for example)
4) Supports both a JIT bytecode generation, and a AOT compiled mode
So I definitely want to keep these in the toy language I will create. But of course, there's one big hole in Clojure...good C/C++ library support. Where Clojure can easily interface with Java, I want this language to easily interface with C (and ideally in both directions...but that might be too hard to support for now). As a consequence, I want the language to support both a JIT'ed and AOT compiled (native) mode.
This is obviously a monumental task. But I think it will force me to become a better Computer Scientist. I will have to get better at many of the fundamentals of CS. And yes, you DO need the things you learn about in school at work (choosing the right data structures, understanding complexity analysis to find poor algorithms, the ability to prove your solution is correct, etc etc). Moreover, I am a firm believer that having learned several languages, and more importantly, different styles of programming has made me a better programmer. When I was interviewing for my new position (at my own company), one of the interviewers noticed that I had Clojure down on my resume. He seemed impressed and curious at the same time (he had heard of Clojure, and did a tiny bit of elisp, but thought lisp was too hard).
My feeling is that all the naysayers of lambdas in the upcoming Java 8 will eventually see their usefulness, instead of just decrying them as a "me too" feature for Java to catch up with C# on the bullet point list. But, much to my surprise, many engineers are loathe to change. I guess that's just one reason I consider myself a scientist rather than an engineer (engineers after all want stability, but scientists, in their quest for truth must be willing to give up the old in order to learn the new).
Sunday, April 1, 2012
A Testing Manifesto for Hardware companies Part 1
I was looking through some of my posts and was looking at some of the "drafts" that I never published. I thought I had published this one earlier, but apparently not. I wrote this draft about a year ago, but I thought it should see the light of day :)
...
I've been an SDET at my company now for about 3.5 years, and I've either seen other companies or divisions and their test strategies, or have talked to other SDETs and Test Engineers from other companies and received an idea of what their company's old test strategies were like. I have since come to several conclusions regarding how testing is done, and how it should be done. What I will write here is primarily of interest to the managers of Testing departments in hardware oriented companies as well as Test Architects, but engineers in the Test department should also find some use of what I shall say.
First off, let me begin with what testing should be:
Is your department not exhibiting some or all of these? Perhaps you don't understand some of what I am talking about? Or maybe (gasp), you think even if your department isn't exhibiting one or more of these traits, that it isn't important? So, let me go into a little more detail into each of these issues, and explain why not following the above is harmful to your organization. Then I will discuss just a few ideas on how to make sure your group is following the above.
Hardware oriented organizations don't understand enterprise level computing
Ok, I know, "enterprise" computing itself doesn't have a definition that's exactly entrenched in stone. But if your SCM or Process group doesn't understand "Software as a service", "distributed computing", or web service technologies (or even doesn't understand remote services or remote procedure calls), then I submit that your organization doesn't understand enterprise level computing. When I say enterprise, I don't necessarily mean high-volume, high-transaction computing environments, but I do mean remote, distributed computing, with at least some level of persistence and data tracking/mining/relationships.
Even should you understand what enterprise computing is about, how would this benefit the test department? Think about what a test group does. It creates tests which are designed to expose defects in the hardware (or the software that controls the hardware). There are many hidden assumption in this seemingly easy enough responsibility. You should immediately think of the following aspects to this:
...
I've been an SDET at my company now for about 3.5 years, and I've either seen other companies or divisions and their test strategies, or have talked to other SDETs and Test Engineers from other companies and received an idea of what their company's old test strategies were like. I have since come to several conclusions regarding how testing is done, and how it should be done. What I will write here is primarily of interest to the managers of Testing departments in hardware oriented companies as well as Test Architects, but engineers in the Test department should also find some use of what I shall say.
First off, let me begin with what testing should be:
- Even Hardware-centric organizations require enterprise techniques
- Hardware-centric organizations need to use fundamental tenets of good software engineering
- Use new but mature technologies suited for the task at hand
- Test Engineers are "true" engineers and should be treated as such
- Managers (Test and Development) need to understand what testing requires
- Don't mix up white box, black box, and acceptance testing
- Test Engineers and Developers have to work hand in hand
- Unit tests should be written by the developers (no "dev test")
- Requirements gathering should be an ongoing process
- Continuous Integration and Deployment is a must
Is your department not exhibiting some or all of these? Perhaps you don't understand some of what I am talking about? Or maybe (gasp), you think even if your department isn't exhibiting one or more of these traits, that it isn't important? So, let me go into a little more detail into each of these issues, and explain why not following the above is harmful to your organization. Then I will discuss just a few ideas on how to make sure your group is following the above.
Hardware oriented organizations don't understand enterprise level computing
Ok, I know, "enterprise" computing itself doesn't have a definition that's exactly entrenched in stone. But if your SCM or Process group doesn't understand "Software as a service", "distributed computing", or web service technologies (or even doesn't understand remote services or remote procedure calls), then I submit that your organization doesn't understand enterprise level computing. When I say enterprise, I don't necessarily mean high-volume, high-transaction computing environments, but I do mean remote, distributed computing, with at least some level of persistence and data tracking/mining/relationships.
Even should you understand what enterprise computing is about, how would this benefit the test department? Think about what a test group does. It creates tests which are designed to expose defects in the hardware (or the software that controls the hardware). There are many hidden assumption in this seemingly easy enough responsibility. You should immediately think of the following aspects to this:
- How are you reporting the results? (are you able to do data mining on results of tests?)
- How are users finding the test tools they need? (given a test case, is there a test tool for it?)
- How are users installing the test tool? (if they found the test tool, how do they install it?)
- How is a user supposed to know how to run the tool? ( Do you maintain elaborate documentation? What arguments are supposed to be passed in for Test Case A versus Test Case B?)
- How are you discovering systems that can run tests? (Can you find systems not in use programmatically, so that you are executing 24/7?)
If your organization isn't linking TestCases to test tools, then I submit that you are in chaos. If your organization isn't storing results of test runs automatically somewhere (hopefully a database of some sort), then you are missing great opportunities. Being able to know what features in the hardware or software are associated with what test tool (and any other metadata required) is absolutely essential. Think about what happens if you don't have this linkage.
Tester- "Hey Sean, is there a script for this test case I got assigned?"
Test Engineer- "What test case is that?"
Tester- "Ummm, let me see, it's ID 00716459"
Test Engineer- "Oh, that's the one to make sure the ioctl in the driver doesn't time out right?"
Tester- "yeah, but is there a program or tool for that?"
Test Engineer-"Yeah there is, let me go find the script on the common share drive"
Tester-"I already kind of looked there..."
Test Engineer-"Did you look under the Sean folder?"
Tester-"Yeah, but there were a couple of scripts that had similar names"
Test Engineer-"Oh yeah...you have to use the one with -version.1.3.5 in it"
Tester-"Oh ok."
Test Engineer-"And did you make sure you installed all the prerequisites on your test machine?"
Tester-"such as?"
Test Engineer-"Well, first you have to install..."
Subscribe to:
Posts (Atom)