ZOMBIE FORUMS

It's a stinking, shambling corpse grotesquely parodying life.
It is currently Thu Mar 28, 2024 10:06 am

All times are UTC - 8 hours [ DST ]




Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 52 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject:
PostPosted: Thu Apr 07, 2005 8:50 pm 
Offline
Addict
User avatar

Joined: Thu Sep 04, 2003 9:43 pm
Posts: 1096
Talauna wrote:
My question How hard is machine code to learn? I never looked too deeply into it but really, how hard is it?

Actually, it pretty much depends on the kind of processor you're targeting. PICs and other small u-processors have reasonably simple instruction sets, while Intel x86 provides a much more complicated (and powerful) set of instructions. If you REALLY want to learn, I'd suggest <a href="http://www.google.com/search?q=PIC+emulator+gnu&sourceid=opera&num=0&ie=utf-8&oe=utf-8">Googling up a free PIC emulator and debugger</a> (there are lots of them floating around) and starting small that way.

In practice though, nobody writes a complete program (for the PC) from scratch in assembly. If you want to be muy macho, learn C. That's plenty hardcore these days. Once you're comfortable with that, you can decide for yourself if you think it's worth writing portions of your code in assembly.

If you're new to programming, I <i>strongly</i> suggest <a href="http://www.python.org/moin/BeginnersGuide">Python</a> instead of C or assembly. I wish we'd had it to learn on in Highschool instead of QBasic. :-?
Python is very easy to learn, easy to debug, the documentation and the development environment are free (no need to pay through the nose for Visual Studio), and it's powerful enough to write real-world software including GUIs, web servers, and other programming languages.

Assembly is easy when you have a good understanding of the concepts behind it. It makes no sense at all if you're not used to thinking in a programmatic way. It is also pretty much useless for expressing complicated concepts.

_________________
Always watching, ever vigilant


Top
 Profile  
 
 Post subject:
PostPosted: Fri Apr 08, 2005 3:02 am 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
Thinman wrote:
If you're new to programming, I strongly suggest Python instead of C or assembly.


Yes, it is, indeed. Python really is pretty good. If I may be so bold, however, let me also recommend you learn Lisp, and you learn it from the masters by reading Structure and Interpretation of Computer Programs by Abelson and Sussman.

For comparison, here is a Quicksort (for signed 32-bit integers only, not for arbitrary types!) written in 386 assembly language, somewhat tuned for Pentium and later processors. If it's gobbedygook, well ... yes, it is. ;-) I can't even promise it works; I'm very rusty. It's probably close, though.

Code:
   .386

vec   equ   8
len   equ   4

   .code

   .align   16

quicksort proc

   cmp   esi, edi   ; if first pos same as last pos, exit
   jbe   done

   mov   eax, dword ptr [esi] ; load eax with pivot

   push   edi         ; save right end of array

   lea   ebx, dword ptr [esi+4]   ; ebx will be left scanning ptr

   jmp   partition

done:   ret

   .align   16

partition:

scan_left:

   cmp   eax, dword ptr [ebx]   ; pivot le [left]?
   jle   scan_right      ; if so, swap this one

   cmp   ebx, edi      ; left >= right?
   jae   recur

   add   ebx, 4
   jmp   scan_left

scan_right:

   cmp   eax, dword ptr [edi]   ; pivot gt [right]?
   jg   swap         ; if so, swap this one

   cmp   ebx, edi      ; left >= right?
   jae   recur

   sub   edi, 4
   jmp   scan_right

swap:

   mov   ebp, dword ptr [ebx]   ; swap the two values
   mov   ecx, dword ptr [edi]   ; note that two different registers
   mov   dword ptr [ebx], ecx   ; used so that hopefully both U and V
   mov   dword ptr [edi], ebp   ; pipes will be filled at least here

   add   ebx, 4         ; advance left pointer
   sub   edi, 4         ; decrement right pointer

   cmp   ebx, edi      ; have they crossed yet?
   jb   partition      ; if not, do more partitioning

recur:

; At this point, eax is the pivot value, esi points to the beginning of the
; array at which the pivot is stored, and ebx points to the values greater
; than the pivot.

   lea   ebp, dword ptr [ebx-4]   ; ebp is one past end of first group

   pop   edi         ; give V pipe something to do
               ; by restoring edi as the end of vec

   mov   ecx, dword ptr [ebp]   ; swap pivot to middle of array

   push   esi         ; give V pipe something to do
               ; by starting to save registers for
               ; recurrence on first group

   mov   dword ptr [esi], ecx   ; finish swapping pivot
   mov   dword ptr [ebp], eax

   mov   esi, ebx      ; esi is now beginning of second group
   sub   ebp, 4         ; ebp is end of first group
   push   ebp         ; save that value for use later

   call   quicksort      ; recur on second group

   pop   edi         ; edi is end of first group
   pop   esi         ; esi is beginning of first group

   jmp   quicksort      ; do tail-call optimisation

quicksort endp

   .align 16

_qsort_int proc

            ; save these registers since most C compilers
   push   esi      ; use them as `register' variables and expect
   push   edi      ; them to be unchanged across subroutine calls

   push   ebx      ; GCC saves this, but MSVC and BCC do not

   push   ebp      ; and this reg is usually a frame pointer

   mov   edi, dword ptr [esp+len]   ; edi is number of elements
   mov   esi, dword ptr [esp+vec]   ; esi is first element
   lea   edi, dword ptr [esi+edi*4-4]   ; edi is last element

   call   quicksort   ; call a recursive version of quicksort that
            ; is not burdened by C calling conventions

   pop   ebp

   pop   ebx
   pop   edi
   pop   esi

   ret

_qsort_int endp


Don't learn assembly language to write it. The point is -- I've spent the last two hours in the middle of the night writing a Quicksort for integers, when sorting integers is probably best done by Radix Sort anyway. I should have been sleeping. (It was an amusing exercise, though.) No, I'm not going to spend the rest of my night squashing the inevitable syntax errors and bugs and whatnot in the code above.

You might learn assembly language to read it, perhaps. It's often very instructive to read the output of your favourite compiler for your favourite language; sometimes you can even see programming errors in the assembly output that aren't obvious in the source code.

The only time you will ever write assembly language is when you want very fine control over your hardware. Graphics programs, such as games, need to control the processor and the video hardware as efficiently as possible. Operating systems need to control all the devices connected to the computer, and high-level languages typically can't do that.

Remember -- a really, really fast program that gives the wrong answer to the problem it is supposed to solve is not worth anything.


Top
 Profile  
 
 Post subject:
PostPosted: Wed Apr 13, 2005 5:50 pm 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
Here's a non-trivial example of the advantages of functional programming: a red-black tree. Compare this small program here with the exact same program in your local C++ standard library and ask yourself which is more understandable and maintainable.

Code:
module RBTree (RBTree, new, insert, lookup, elems, empty) where

data Colour = Blk | Red

data Ord a => RBTree a = Lf
                       | Br (RBTree a) a Colour (RBTree a)

new :: RBTree a
new = Lf

insert :: Ord a => a -> RBTree a -> RBTree a
-- Add an element to a tree.
insert x = blkRoot . ins_x
    where
    blkRoot Lf = error "tree is empty after insertion"
    blkRoot (Br l y _ r) = Br l y Blk r
    lbal  (Br (Br (Br lll lly Red llr) ly Red lr) y Blk r)
        = (Br (Br lll lly Blk llr) ly Red (Br lr y Blk r))
    lbal  (Br (Br ll ly Red (Br lrl lry Red lrr)) y Blk r)
        = (Br (Br ll ly Blk lrl) lry Red (Br lrr y Blk r))
    lbal  (Br (Br ll ly Red lr) y Blk (Br rl ry Red rr))
        = (Br (Br ll ly Blk lr) y Red (Br rl ry Blk rr))
    lbal t = t
    rbal  (Br l y Blk (Br rl ry Red (Br rrl rry Red rrr)))
        = (Br (Br l y Blk rl) ry Red (Br rrl rry Blk rrr))
    rbal  (Br l y Blk (Br (Br rll rly Red rlr) ry Red rr))
        = (Br (Br l y Blk rll) rly Red (Br rlr ry Blk rr))
    rbal  (Br (Br ll ly Red lr) y Blk (Br rl ry Red rr))
        = (Br (Br ll ly Blk lr) y Red (Br rl ry Blk rr))
    rbal t = t
    ins_x Lf = Br Lf x Red Lf
    ins_x (Br l y c r) | x < y     = lbal $ Br (ins_x l) y c r
                       | x > y     = rbal $ Br l y c (ins_x r)
                       | otherwise = Br l x c r

lookup :: Ord a => a -> RBTree a -> Maybe a
-- Find whether or not an element is in an RBTree, and if it is, return it.
lookup x = lu_x
    where
    lu_x Lf = Nothing
    lu_x (Br l y _ r) | x < y     = lu_x l
                      | x > y     = lu_x r
                      | otherwise = Just y

elems :: RBTree a -> [a]
-- Get a list of all elements in an RBTree, in infix order.
elems t = elemsLambda t []
    where
    -- elemsLambda :: RBTree a -> [a] -> [a]
    elemsLambda Lf = id
    elemsLambda (Br l x _ r) = (elemsLambda l) . (x :) . (elemsLambda r)

empty :: RBTree a -> Bool
--Query whether or not an RBTree has no elements in it.
empty Lf = True
empty _  = False


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 14, 2005 4:46 pm 
Offline
Addict
User avatar

Joined: Thu Sep 04, 2003 9:43 pm
Posts: 1096
I'm already convinced I need to take a look at Haskell when I have time, but this example code gives me the fear.

_________________
Always watching, ever vigilant


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 14, 2005 10:44 pm 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
Is that good fear, like Alien? Or bad fear, like Friday the Thirteenth Part N+1?

*looks insane*


Top
 Profile  
 
 Post subject:
PostPosted: Thu Apr 14, 2005 10:47 pm 
Offline
User avatar

Joined: Sun Jan 17, 2038 9:00 pm
Posts: 3209
Tamayo wrote:
Is that good fear, like Alien? Or bad fear, like Friday the Thirteenth Part N+1?

*looks insane*

But Alien was "I'm going to piss myself" fear!


Top
 Profile  
 
 Post subject:
PostPosted: Fri Apr 15, 2005 12:44 pm 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
The Baron wrote:
But Alien was "I'm going to piss myself" fear!


We can't have people wetting their pants. That would be uncivilised, and *pokes self with large stick* inappropriate for the Debate Club forum. So, I will metaphorically spoil the movie (Ripley gets away! With the cat!) and look through the above code in some detail.

The most important function above is, of course, insert. Its type annotation is Ord a => a -> RBTree -> RBTree a, which means, "this is a function on any type that accepts a total ordering, such that given an element of that type and a red-black tree over that type, a new red-black tree will be returned."

The whole definition of insert is insert x = blkRoot . ins_x. That is a curried definition: though insert notionally takes two parameters, what it really does is take an element and return a function from trees to trees that depends upon that element.

The period in the expression blkRoot . ins_x is the operation of composition, usually written as a small circle in mathematical texts, but ASCII doesn't have little circles. Thus, that expression is equivalent to \ t -> blkRoot(ins_x(t)). Hint: the backslash character in Haskell represents "lambda".

The functions ins_x and blkRoot are entirely contained as sub-functions of insert, after the "where" keyword. Haskell is a fully block-structured language, in that variables in outer functions are available to inner functions; this is not the case, for example, in C++. (Yes, it's possible to define inner functions in C++, but it's somewhat tricky, and you don't get access to the outer functions' data, so there's not much point in doing it. Exercise for the reader.)

ins_x inserts the value of the outer function's parameter x into a red-black tree. It follows the ordinary binary-search-tree algorithm for insertion on the way down the tree, but then fixes up the tree afterward for violations of the red-black principles.

Most imperative implementations do the fixing on the way down as well, and require far more code to do it; naturally, it's slightly faster to do it that way, but there are a few drawbacks: top-down colour adjustments are almost necessarily destructive, so the tree is thereby changed in place and is thus not persistent across updates, and they are much more complicated.

In the code above, the balancing is done by the rbal and lbal functions (for red-black violations on the right and left respectively) but that is something of an optimisation. Let us consider an alternate function:

Code:
bal :: RBTree a -> RBTree a
bal  (Br (Br (Br lll lly Red llr) ly Red lr) y Blk r)
   = (Br (Br lll lly Blk llr) ly Red (Br lr y Blk r))
bal  (Br (Br ll ly Red (Br lrl lry Red lrr)) y Blk r)
   = (Br (Br ll ly Blk lrl) lry Red (Br lrr y Blk r))
bal  (Br l y Blk (Br rl ry Red (Br rrl rry Red rrr)))
   = (Br (Br l y Blk rl) ry Red (Br rrl rry Blk rrr))
bal  (Br l y Blk (Br (Br rll rly Red rlr) ry Red rr))
   = (Br (Br l y Blk rll) rly Red (Br rlr ry Blk rr))
bal  (Br (Br ll ly Red lr) y Blk (Br rl ry Red rr))
   = (Br (Br ll ly Blk lr) y Red (Br rl ry Blk rr))
bal t = t


One can replace all references to lbal and rbal in the original program with references to this bal and it will still work. (Slightly, very slightly more slowly.) However, looking at this bal shows all the distinct rotations required by the red-black tree structure together, and hopefully understandably. In order, then, the clauses mean:

  • When at the root of a tree with a red left subtree that has a red left subtree, do a double right rotation.
  • When at the root of a tree with a red left subtree that has a red right subtree, do a right-left rotation.
  • When at the root of a tree with a red right subtree that has a red right subtree, do a double left rotation.
  • When at the root of a tree with a red right subtree that has a red left subtree, do a left-right rotation.
  • When at the root of a tree with two red subtrees, redden the root and blacken the subtrees.
  • Otherwise, don't do anything.


The only other really funny thing I did in the above program was in the elems function, which performs an infix traversal of an RBTree and returns all the elements of the tree in an ordinary list. I gave a hint in the original definition of that function of what kind of trick I was pulling; I'll let you figure out what it was.


Top
 Profile  
 
 Post subject:
PostPosted: Tue May 24, 2005 12:08 pm 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
For people accustomed to imperative languages who are interested in learning Haskell: try http://www.haskell.org/~pairwise/intro/intro.html, which was written by a fellow who wanted to use Haskell to build a video game. (Links to the latter are found in the article.)


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 10, 2005 4:43 am 
Offline
<font color=red><b>STALKER/FAG ALERT.
User avatar

Joined: Sun Jun 20, 2004 2:38 am
Posts: 1579
I like Matlab, if only because it's a better language than the other one I know, which is TurboPascal.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Aug 04, 2005 7:28 pm 
Offline
User avatar

Joined: Sun Jan 17, 2038 9:00 pm
Posts: 3209
Bump of Old Thread:

Structure and Interpretation of Computer Programs is available online. It is good. It is whoa good.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 6:29 am 
Offline
Expatriate
User avatar

Joined: Fri Oct 15, 2004 9:44 pm
Posts: 134
Location: Screaming obsenities regarding untestable C++ software.
At one point I believed the sole purpose of LISP was to make first year students change thier major to Drama.

Since then, I've realized that the primary purpose of LISP has been to deter all but the most hardcore of computer programmers from changing the default Emacs settings.

_________________
"Their need for total domination and to bring the world to the edge of utter apocalypse makes them less-than-ideal Jenga partners."


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 9:43 am 
Offline
Addict
User avatar

Joined: Fri Nov 08, 2002 5:00 pm
Posts: 4439
Location: You can't take the sky from me. Since I found Serenity.
Pffft. Emacs.

_________________
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 11:29 am 
Offline
User avatar

Joined: Sun Jan 17, 2038 9:00 pm
Posts: 3209
Emacs is a weapon of the Gods, second only to Durandal itself.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 12:40 pm 
Offline
PostWhorePornStar
User avatar

Joined: Fri Jan 17, 2003 5:00 pm
Posts: 7672
Location: Tallahassee, FL
VI BITCHES!


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 6:24 pm 
Offline
Addict
User avatar

Joined: Fri Nov 08, 2002 5:00 pm
Posts: 4439
Location: You can't take the sky from me. Since I found Serenity.
krylex wrote:
VI BITCHES!


Preach on brudda!

_________________
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.


Top
 Profile  
 
 Post subject:
PostPosted: Tue Aug 09, 2005 8:39 pm 
Offline
Addict
User avatar

Joined: Thu Sep 04, 2003 9:43 pm
Posts: 1096
Ylis wrote:
At one point I believed the sole purpose of LISP was to make first year students change thier major to Drama.

Since then, I've realized that the primary purpose of LISP has been to deter all but the most hardcore of computer programmers from changing the default Emacs settings.

Wusses.

If you can learn perl, you can surely learn lisp.
In fact, I've heard cogent arguments for classifying perl as a superset of lisp...


Quite a while ago, Tamayo wrote:
Is that good fear, like <i>Alien</i>? Or bad fear, like <i>Friday the Thirteenth Part N+1</i>?

I was thinking crazy-fear, like <i>Fear and Loathing in Las Vegas</i>:
<i>"My god man, we can't stop HERE... THIS IS BAT COUNTRY!"</i>

_________________
Always watching, ever vigilant


Top
 Profile  
 
 Post subject:
PostPosted: Wed Aug 10, 2005 12:25 pm 
Offline
User avatar

Joined: Sun Jan 17, 2038 9:00 pm
Posts: 3209
NOT BAT COUNTRY!

and I just got Krykry to install Emacs on the ES/CAS/EN server. Ohoho!

Code:
Krykry: getting emacs for you
Krykry: pansy
Barry: god damn right
Barry: ohboy!
Barry: it runs!
Krykry: HOW DO I GET OUT OF THIS ABOMINATION!
Barry: control-x control-c
Krykry: :q DOES NOT WORK!
Barry: C-x C-c
Krykry: made it
Krykry: phew
Krykry: I was almost a gonner
Barry: you have just taken your first step on the path to enlightenment


Top
 Profile  
 
 Post subject:
PostPosted: Wed Aug 10, 2005 12:58 pm 
Offline
Native
User avatar

Joined: Wed Dec 11, 2002 5:00 pm
Posts: 869
Thinman wrote:
In fact, I've heard cogent arguments for classifying perl as a superset of lisp...


Here's one argument. Whether or not it is cogent is for you to decide.

Lisp, as it was first devised, is a notation for the typeless lambda calculus. That means that not only are functions first-class values, but functions are in a real sense the only values. All other values are expressed in terms of functions.

Nobody uses Lisp like that, though, not since it left the world of the logician's blackboards and entered the computer programmer's Emacs editors. (Emacs is the One True Program.) From a computer programmer's point of view, there do exist all within the programming language many kinds of non-function values, like integers and characters and symbols -- and, naturally, llists of those things -- but there also exist function values.

A Lisp function, true to its origin as a notation for the lambda calculus, is an expression that binds a list of names into an expression. That is, as a grammar fragment:

<fn-expression> ::= '(' 'lambda' '(' <args-list> ')' <expression> ')'
<args-list> ::= { <identifier> }
<expression> ::= any kind of Lisp expression
<identifier> ::= any legal Lisp name

(Experienced Lisp programmers will note that the argument list of a lambda expression can include a few other things, such as for example optional arguments, but it's outside the scope of my discussion to mention them. Besides, Perl functions can do that too ....)

Here, then, is a simple Lisp function.

Code:
(define my-map
  (lambda (f l)
    (if (null? f)
        nil
      (cons (f (car l))
            (my-map f (cdr l))))))


There exists a Perl expression for the above function:

Code:
sub my_map (&@) {
  my ($f, @l) = @_;

  if (scalar @l == 0) {
    return ();
  } else {
    return unshift(&f($l[0]), my_map(f, shift @l));
  }
}


As I noted above, though, functions are first-class values in Lisp. Let's perform a simple transformation on map above, called currying, to illustrate that fact.

Code:
(define curried-map
  (lambda (f)
    (let
        ((inner (lambda (l)
                  (if (null? l)
                      nil
                    (cons (f (car l))
                          (inner (cdr l)))))))
      inner)))


This version of the map combinator takes a function, f, and returns a new function which takes a list, l, and applies f to each element of the list. The latter function is a very basic example of a closure. Languages like C cannot produce closures, though C++ can emulate closures with classes that overload the application operator. Perl, however, can do it natively:

Code:
sub curried_map (&) {
  my $f = shift;

  sub inner (@) {
    my @l = shift;

    if (scalar @l == 0) {
      return ();
    } else {
      return unshift (&f($l[0]), &inner($f, shift @l));
    }
  }

  return inner;
}


The above examples show how the Perl keyword "sub" is almost exactly equivalent to the Lisp keyword "lambda" -- and that is why Perl is a dialect of Lisp.

Edit: fixed a bug


Last edited by Tamayo on Sun Sep 11, 2005 3:39 am, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Sat Sep 10, 2005 10:39 pm 
Offline
<font color=red><b>STALKER/FAG ALERT.
User avatar

Joined: Sun Jun 20, 2004 2:38 am
Posts: 1579
krylex wrote:
However, what is pretty much the largest company on the face of the planet? It makes more money in a quarter than a great deal of nations of the world do in a year.

I'll give you a hint, Billy Gates is the principal shareholder.


Actually, Wal-Mart is the biggest company in the world, according to this.

Microsoft is #41.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Sep 11, 2005 2:57 am 
Offline
User avatar

Joined: Sun Jan 17, 2038 9:00 pm
Posts: 3209
nick012000 wrote:
krylex wrote:
However, what is pretty much the largest company on the face of the planet? It makes more money in a quarter than a great deal of nations of the world do in a year.

I'll give you a hint, Billy Gates is the principal shareholder.


Actually, Wal-Mart is the biggest company in the world, according to this.

Microsoft is #41.

that particular list is not well-liked because it bases company size on total revenues, not profits, which means it is totally biased towards retailers.

_________________
election results: still an op
Let me put it to you this way: I earned capital in the campaign, political capital, and now I intend to spend it. It is my style.


Top
 Profile  
 
Display posts from previous:  Sort by  
Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 52 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 30 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group