- Network+: I have begun to work through the Network+ manual and I think I should be ready for the exam in about 3 months.
- Assembly Language: I have worked through "Professional Assembly Language" (Blum 2005), and have come up with a small practical project to implement in assembly language. I will be working on a command-line programmable RPN calculator, details to follow.
- Writing: The MIT open courseware is not heading in the right direction since it only has the assignments online. I think I need something that provides more of a framework of how and what I should be trying to accomplish.
- Linear Algebra: I have begun the MIT video course on Linear Algebra (18.06) and I think the video series is a good way to engage with the material. It's interesting how differently we learn from lectures vs. learning from books. I have always thought that I learn better by reading, but there is a certain way that we learn how to work through a problem when we participate in working through the problem with a teacher.
2.27.2010
Evaluating My Direction
2.18.2010
Assembly Language - Command line parameters
I ran into a problem with the way that command line parameters are passed in Assembly Language. The book I'm working through has a couple example programs illustrating how to access the command line arguments and none of these examples worked on my system. The simple solution was that, at some point between this book being written and me reading it, this convention had changed. Instead of the stack looking like it does in the book, with all the command line arguments on the stack, we have the number of parameters first and then a pointer to a pointer to all the parameters in null terminated strings.
This is how it looks in the old style: number: 3 *p1: program name *p2: param1 *p2: param2 And this is how it looks in the new style: number: 3 *p: *params *params: param1, param2, ...
I should have guessed this from the C calling convention **args, but it took a fair bit of digging with GDB to analyze what exactly was going on with the stack. So, the end result: A program to print all the command line arguments:
.section .data output: .asciz "parameter: %s\n" .section .bss .section .text .globl main main: nop movl (%esp), %ebx movl 4(%esp), %ecx # Num parameters movl 8(%esp), %ebx # This is a pointer to the string pointer movl (%ebx), %edi # This should be the string pointer loopargs: pushl %ecx pushl %edi pushl $output call printf addl $8, %esp movl $0x255, %ecx movb $0, %al cld repne scasb popl %ecx loop loopargs nop movl $1, %eax movl $0, %ebx int $0x80
2.13.2010
px Language - Speed Tests
In order to more fully understand how I'm going to implement the translator from my imaginary programming language, I have written a few direct translations from px to assembly. My thinking is that if the language doesn't rely on the abstractions provided by the "compile to C" interpreted languages, I should be able to end up with a systems level language with the clean syntax of python, ruby, et al.
My first example is to calculate the sum of a large list. Here are two versions in python.
UPDATE!!! After trying a few more versions, I realized that my loop counters were off in every example. I had made the silly python mistake of forgetting the range of range. range(0, 123456789) = 0,1,2...123456788. And I had subsequently propagated that mistake into my C and Assembly versions, producing the wrong answer in every case, sometimes very fast! Lesson learned: Check your math!
# listsum1.py - calculate 1 + 2 + ... + 12,345,678 = listsum listsum = 0 for f in range(0,12345678): listsum = listsum + f print "The result is " + str(listsum) # listsum2.py listsum = sum(range(0,12345678)) print "The result is " + str(listsum)
And here's what it might look like in px.
print listsum buildlist 12345678
But, of course, no library functions exist yet, so I'll spell out how the functions listsum and buildlist would be defined.
n... buildlist size, next 0: next next + 1 n next if next < size : n listsum list...: break if not list n n + list continue True :
buildlist is defined as taking one argument, size and producing a list, one item at a time. Listsum consumes these items and produces a final value when the whole list has been read. All items are passed as two 32-bit values, [type/status] and [value/pointer]. Each operation checks the status flag to check if it is receiving a valid object and what that object is exactly. The buildlist function uses this fact to push a false object onto the stack when it reaches "size". This tells listsum that there are no more values to be read. In assembly this is what the code structure looks like in simplified form:
list_size: .int 12345678 l_sum: .int 0 push $1 push list_size pop list_size pop edi #using edi as the status flag mov 0, ecx #and ecx for the counter buildlist: compare list_size, ecx cmovae 0, edi #if above, set edi to 0 (false) add 1, ecx push edi push ecx listsum: pop eax pop edi cmp 0, edi je end_listsum add eax, l_sum jmp buildlist end_listsum print l_sum
In the actual implementation, I changed the add to support a quadword because the results get large quite fast, but this gives you the idea.
Is It Fast?
Well, I knew it would be fast, but this is a pretty large list, the code between buildlist and end_listsum has to run over 12 million times to calculate the sum, this is what I got when comparing the two python versions and my assembly version:
$ time python listsum1.py The result is 76207876467003 real 0m15.379s user 0m14.819s sys 0m0.557s $ time python listsum2.py The result is 76207876467003 real 0m8.123s user 0m7.476s sys 0m0.647s $ time ./listsum The result is 76207876467003 real 0m0.275s user 0m0.273s sys 0m0.000s
That's pretty blazing fast if you ask me! But I was put in my place when I ran the C version which produced these results:
time ./f_sum3 The answer is 76207876467003.000000 real 0m0.123s user 0m0.120s sys 0m0.000s
I used a floating point double for the list sum, so maybe that's why C was faster. Still, if we use C as the baseline we have:
C 1 px 2.2 Py2 66.04 Py1 125.03
Not bad for a start. Now I'm off to dig through the compiled C code to see how it should be done...
UPDATE #2 - I've realized that there is a quite simple algorithm to solve this particular problem and that is: (n/2) * (n+1). This simple equation eliminates the loop completely making the calculation trivial. The updated python version runs in 0.038s and the C version runs in 0.002s producing the, now correct sum, 76207888812681.
2.11.2010
px Language - Parsing Challenges
After spending most of the day investigating parsers, lexers and compiler compilers, I've come to the conclusion that my language doesn't really need these just yet. I've really only outlined three syntactic rules and two structural ones, and these cover all the ground I can see in front of me.
Syntax
1. Right to left evaluation, except inside parentheses:
z y if (y > x) z x if (y2. Right to left definition of block header line:
z function z, y: z do_something y :3. Comma seperated values are globbed together into an array.
process_list x, y, 12, 72, "Hello World!"
That's basically it for the syntax, where it gets interesting is namespaces and typing.
Structure
Every code block defines it's own namespace by default. This means that every block of code is explicit in defining what values it is using. Here's a trivial block which takes two operands and produces another:
.z a_function .z, y: .z y + .z
The ".", and the lack thereof, are the essential parts when it comes to namespaces. You might have seen the dot syntax in other languages (my_array.append()) and it's not really that different in px, except that referencing variables is a two way street. a_function is declaring it's own namespace under the main program and thus becomes main.a_function. That's fine, everything in the main namespace can access it directly by it's bare name and we can keep stacking them just like in other languages.
But the trick here is the preceding '.' on the variable name z and the lack of it on y. What's actually going on here? What happens is that the function is defined with concrete references to the z in the parent namespace and one reference to a y which does not exist. This becomes a unary function, a partially applied function and is never called until it is supplied with a y. When it does get called with a value, the z in the parent namespace gets updated accordingly. This function might be more appropriately called "increment_z", let's see it in action:
.z 10 increment_z 1 print z >>11 increment_z 8 print z >>19
A standard for loop imports all names, but it does so explicitly in it's function definition. "Hold on," you might ask, "it's function definition???" How does a for loop have a function definition? Don't other languages define this as built in to the language? The answer is yes, but in px I have decided to expose all the gory details of language design to the programmer, and only hardcode the bare essentials. This is roughly how the standard loops are implemented as blocks:
.* loop .*, _start, _end: break _end condition continue _start condition :
The _start and _end tags are handles for the final assembly language implementation. The * wildcard states that any and all of the parent namespace will be accessible. This block definition has no pre-determined outputs or effects and so it's considered a function template. If called, the break and continue expressions will only be included if their conditions are met. Here's how that might look:
loop: break if .x
Loop doesn't actually control the looping, the statements within it do. We could have omitted the break statement and used the condition of the continue to control the loop. Notice again that this block is a fully defined namespace and all external references must be used accordingly.
To summarize namespaces, block = namespace = object = method = class = control mechanism = symbol. If a block has fully defined inputs and outputs, it is treated just like any other literal value in the flow.
Types
I've stated that there are two structural elements to my language: Namespaces and Types. Well, I kind of lied: there's only one types are also implemented functionally, but I haven't worked out how and how much of the checking can be done in the final assembly code. The general idea is this: values that aren't known at compile time are put on the heap and indexed with a hash table. Values that are know (by single literal assignment, or explicit typecasting) are put on the stack / data segment. Type statements are just like any unary operator:
x number 225.993 y int 235 z string "Please assign me to z!"
They go right next to the value being assigned as a check for the correctness of the data being passed to it.
2.10.2010
px Language
x, y 20, 15 z 42 z x if x > y z y if y > z print zx, y and z are assigned the values 20, 15 and 42. y and x are pushed onto the stack and '>' pops them and compares them, putting a 0 or 1 on the stack. The if statement takes two operands, the x and the boolean result of the '>' operation. It then pushes onto the stack x and [0/1] (secret rule #1). Secret rule#1: Values are always stored in two parts, a value and a flag. If the flag is false the assignment doesn't happen. I have chose to omit the assignment operator, because all evaluations logically flow right to left. You will see the benefit of using infix operators if you reduce this operation to it's RPN form, with parens added for clarity: z (if ( x (> y x))) The > and other mathematical terms can be understood with some practice in RPN, but the if statement is not very intuitive at all without infix notation. Another curiosity that needs addressing is that since this is stack-based assignment, the first assignment "x,y 20,15" just adds the numbers 15 and 20 onto the stack and then pops them off making y=20 and x = 15. Not the preferred functionality! Functions Simple enough for basic expressions, how do we implement more complex functions? I've carried the same logic into function expressions. Functions always produce the left-hand value based on the right-hand input, but you add a code block below the statement line. This is how it looks in practice:
x 15 y 12 .x some_function .x, .y: .x sum(.x, .y) : print xI almost went with the Python-esque whitespace-significance, but have decided for now to close blocks with a final colon. The function's header defines it's inputs and outputs. The function takes two values, x and y, passes them through the function block and produces x. There are no return statements, because the output symbol is explicitly given in the header line. Okay, the syntax is simple enough, but what can you do with it, and what are the leading periods all about? That's where namespaces come into play... Namespaces Each block defines it's own namespace. The previous function declared inputs of .x and .y. These are concrete references to the parent namespace. The output was also a concrete reference, so the function was fully defined and executed to produce the new value of x. Here's an example that, although it looks very similar, is actually quite different:
x 15 y 12 m generic_function m, n: m sum(m, n) : x generic_function x, y print xThis is more like normal function you would use, because it defines the function with generic inputs and outputs and then you use them on specific values. The function is only executed when called with some specific values. This opens the door for partially applied functions and the like. eg:
m part_func .x, m: m sum(.x, m) : y part_func y m const_function .x, .y: print x, y m True : res const_function .x defined_out m, n: .x sum(m, n) : defined_out 8 1024 print xThis is a simple but powerful way to implement a lot of the functionality of high level language with only one syntactic convention. One final note about namespaces is that the .* symbol references the entire parent namespace. This allows one to implement transparent code blocks like loops. Eg:
x 0 x_max 11 .* loop_block .*: continue .x < .x_max print .x .x .x + 1 loop True :Because the input and output are fully defined, the code executes and can access any of the variables, functions etc. of the parent block via the dot syntax. The loop and continue functions control the flow of the block and can be used in any block. 'loop' is just a "goto $start if expression is true" statement and 'continue' is a "goto $end if expression is false" statement. This block first checks it's condition, breaking if it is false, does some more stuff and then loops back to the start unconditionally. Alternately, one might want to omit the 'continue' statement and do the condition check with the 'loop' statement. Every block will have a start and end tag that can be used in this manner. Objects Because blocks are self-contained namespaces, there is another possible use for them, classes and objects.
. some_object .: name "some_object" value 42 :This block didn't specify any inputs or outputs. It is thus a concrete object which can be used as follows:
print some_object.nameBut maybe I'm getting ahead of myself! Stay tuned for more developments and please give suggestions on the name, I'm not sure how or why I came up with "px".
2.09.2010
CompTia A+ - Exam Objectives
Assembly Language - Development Environment
Writing and the Environment - Exercise 2a
2.05.2010
Exercise 1b: Writing and the Environment
Assembly Language - Instruction Codes
Instruction code <- Instruction Pointer <- Memory Data <- Instruction code (Data Element, opt.) Data <- Registers Data <- Data pointer <- MemoryEach instruction code can perform operations on data from the registers, main memory, or it's own 1-4 byte data elements. The actual instruction code can be from 1 - 17 bytes long, the only required byte(s) being the opcode which tells the processor what operation to perform. The other bytes of the instruction code specify modifiers for the operation and data elements (0-4 bytes) for the operation. Data registers are essentially memory locations on the processor itself. This makes them the fastest way to store bits of information, but the space is very limited (x86 defines eight 32bit registers). Assembly language adds a layer of abstraction to this by adding mnemonics for the opcodes.
55 89 E5 83 EC 08Translates to:
push %ebp mov %esp, %ebp sub $0x8, %espIt also lets you declare and name your data.
testvalue: .long 150 message: .ascii "This is a test message." pi: .float 3.14159In summary, assembly language may look extremely cryptic, but it is at least human-readable and it gives the programmer access to the core of a CPU's processing. So here's my first assembly language program:
# cpuid.s Sample program to extract the processor Vendor ID .section .data output: .ascii "The processor Vendor ID is 'xxxxxxxxxxxx'\n" .section .bss .section .text .globl _start _start: movl $0, %eax cpuid movl $output, %edi movl %ebx, 28(%edi) movl %edx, 32(%edi) movl %ecx, 36(%edi) movl $4, %eax movl $1, %ebx movl $output, %ecx movl $42, %edx int $0x80 movl $1, %eax movl $0, %ebx int $0x80Which I assembled and linked with the following commands:
$ as -o cpuid.o cpuid.s $ ld -o cpuid cpuid.oAnd the output:
$ ./cpuid The processor Vendor ID is 'AuthenticAMD'Hooray!
2.04.2010
Bluebrain Project
This is not directly related to my studies at the moment, but I will be keeping my eye on this project.
Bluebrain | Year One from Couple 3 Films on Vimeo.
Although much more lofty and ambitions than what I would like to be involved in (for now, anyway!), the project is interesting in it's medical focus of the benefits of brain modeling. I have noticed that when the focus is computation, the immediate payoffs are better (ie. interesting algorithms, programming structures), but we always lose sight of the bigger pictures and run off into premature optimization. The pocket calculator does computation faster than any brain, but it will never get beyond its programming.
Exercise 1a: Writing and the Environment
Course Planning
2.03.2010
Studying Outside The Classroom
Blog Archive
-
▼
2010
(55)
-
▼
February
(14)
- Evaluating My Direction
- Assembly Language - Command line parameters
- px Language - Speed Tests
- px Language - Parsing Challenges
- px Language
- CompTia A+ - Exam Objectives
- Assembly Language - Development Environment
- Writing and the Environment - Exercise 2a
- Exercise 1b: Writing and the Environment
- Assembly Language - Instruction Codes
- Bluebrain Project
- Exercise 1a: Writing and the Environment
- Course Planning
- Studying Outside The Classroom
-
▼
February
(14)