Archive for July, 2008

Unifying Scheme numbers and arithmetic

Thursday, July 31st, 2008

Although display could output all three number formats, read could not. I’ve now added the necessary code to read in negative numbers, and to create an absolute zero number.

The procedures for addition and subtraction have been modified to remove digit constants. As an example, the nine’s complement procedure now looks like this…

      (nines-complement
        (lambda (x)
          (cond
            ( (eq? x digit0) digit9 )
            ( (eq? x digit1) digit8 )
            ( (eq? x digit2) digit7 )
            ( (eq? x digit3) digit6 )
            ( (eq? x digit4) digit5 )
            ( (eq? x digit5) digit4 )
            ( (eq? x digit6) digit3 )
            ( (eq? x digit7) digit2 )
            ( (eq? x digit8) digit1 )
            ( (eq? x digit9) digit0 )
          )
        )
      )

The result is that I can now use the numbers generated by read and outputted by display by changing some letrec definitions…

      (num-mark (car 1))
      (psign (car(cdr  1)))
      (msign (car(cdr -1)))
      (zsign (car(cdr  0)))

      (digit0 (integer->octet 0))
      (digit1 (integer->octet 1))
      (digit2 (integer->octet 2))
      (digit3 (integer->octet 3))
      (digit4 (integer->octet 4))
      (digit5 (integer->octet 5))
      (digit6 (integer->octet 6))
      (digit7 (integer->octet 7))
      (digit8 (integer->octet 8))
      (digit9 (integer->octet 9))

With the add procedure doing both addition and subtraction of magnitudes, the subtract procedure requires only the additional support of a negation procedure.

      (subtract
        (lambda (x y)
          (cond
            ( (eq? (car x) num-mark)
              (cond
                ( (eq? (car y) num-mark) (sub-num x y) )
                ( #t                     '***undefined*** )
              )
            )
            ( #t '***undefined*** )
          )
        )
      )

      (sub-num
        (lambda (x y)
          (add-num x (negate y))
        )
      )

      (negate
        (lambda (x)
          (cond
            ( (eq? (car(cdr x)) zsign) x )
            ( (eq? (car(cdr x)) psign) (cons num-mark (cons msign (cdr(cdr x)))) )
            ( (eq? (car(cdr x)) msign) (cons num-mark (cons psign (cdr(cdr x)))) )
            ( #t '***undefined*** )
          )
        )
      )

Scheme arithmetic, subtraction

Wednesday, July 30th, 2008

Subtraction is performed by using ten’s complement, which is nine’s complement + 1. The sub-magnitude procedure supplies the +1 as the carry argument to sub-mag1. Because the second operand is being negated, it is “sign extended” with a 9 digit, while the first operand is still sign extended with a 0 digit.

      (nines-complement
        (lambda (x)
          (cond
            ( (eq? x '_0) '_9 )
            ( (eq? x '_1) '_8 )
            ( (eq? x '_2) '_7 )
            ( (eq? x '_3) '_6 )
            ( (eq? x '_4) '_5 )
            ( (eq? x '_5) '_4 )
            ( (eq? x '_6) '_3 )
            ( (eq? x '_7) '_2 )
            ( (eq? x '_8) '_1 )
            ( (eq? x '_9) '_0 )
          )
        )
      )

      (sub-magnitude
        (lambda (x y)
          (cons num-mark (adjust-mag1 (sub-mag1 x y '_1)))
        )
      )

      (sub-mag1
        (lambda (x y carry)
          (cond
            ( (null? x)
              (cond
                ( (null? y)
                  (list (car (add-digit '_0 '_9 carry)))
                )
                ( #t
                  (cons
                    (car (add-digit '_0 (nines-complement (car y)) carry))
                    (sub-mag1
                      '()
                      (cdr y)
                      (car (cdr (add-digit '_0 (nines-complement (car y)) carry)))
                    )
                  )
                )
              )
            )
            ( (null? y)
              (cons
                (car (add-digit (car x) '_9 carry))
                (sub-mag1
                  (cdr x)
                  '()
                  (car (cdr (add-digit (car x) '_9 carry)))
                )
              )
            )
            ( #t
              (cons
                (car (add-digit (car x) (nines-complement (car y)) carry))
                (sub-mag1
                  (cdr x)
                  (cdr y)
                  (car (cdr (add-digit (car x) (nines-complement (car y)) carry)))
                )
              )
            )
          )
        )
      )

A positive result propagates leading zeroes, while a negative result will propagate leading nines. A subtle point with addition was the prevention of adding a leading zero. With subtraction, the extra digit is needed to ensure that a leading nine of a positive result is not misinterpreted as the minus sign.

Because of big-Endian representation, we need to search for the last digit in the list…

      (neg-mag?
        (lambda (x)
          (cond
            ( (null? (cdr x)) (eq? (car x) '_9)  )
            ( #t              (neg-mag? (cdr x)) )
          )
        )
      )

The test for negative result is then used to choose whether or not to complement the result. The complementation is basically a subtract-from-zero…

      (adjust-mag1
        (lambda (x)
          (cond
            ( (neg-mag? x) (cons msign (trim-mag1 (recomplement x))) )
            ( #t           (check-zero (cons psign (trim-mag1 x))) )
          )
        )
      )

      (recomplement
        (lambda (x)
          (sub-mag1 '() x '_1)
        )
      )

The final magnitude will have at least one digit that will need to be removed. The easiest way is to reverse the list, chop off the leading digit, then reverse it again. As a space-saving effort, leading zeroes will be suppressed. And if all digits have disappeared, the result is a zero.

      (trim-mag1
        (lambda (x)
          (reverse (behead-zero (cdr (reverse x))))
        )
      )

      (behead-zero
        (lambda (x)
          (cond
            ( (eq? (car x) '_0) (behead-zero (cdr x)) )
            ( #t                x )
          )
        )
      )

      (check-zero
        (lambda (x)
          (cond
            ( (null? (cdr x)) (list zsign) )
            ( #t              x )
          )
        )
      )

Scheme arithmetic, addition

Tuesday, July 29th, 2008

I continue on the unconventional Lisp/Scheme implementation path by creating arithmetic through symbolic methods. On the one hand, it’s terribly inefficient. On the other, it’s a model for “bignum” processing.

Below, we start with the representation, and a procedure for displaying it. The procedure test-arith shows the three basic formats for decimal integers. Although zeros are supposed to be represented with just the zsign marker, it is possible to create several +0 and -0 representations. The digit order is little-Endian, which puts the one’s (or unit’s) digit at the leftmost position. The procedure display-digit, which is not shown here, uses knowledge of the base system to display exactly one digit.

The procedure display, from the base system, displays numbers that are internally structured similarly to the numbers used below.

      (num-mark 'num_mark)
      (psign '+)
      (msign '-)
      (zsign '_0)

      (display-num
        (lambda (x)
          (cond
            ( (eq? (car(cdr x)) psign)
              (display-num1 (cdr(cdr x)))
            )
            ( (eq? (car(cdr x)) zsign)
              (display 0)
            )
            ( (eq? (car(cdr x)) msign)
              (display '-)
              (display-num1 (cdr(cdr x)))
            )
            ( #t '***undefined*** )
          )
        )
      )

      (display-num1
        (lambda (x)
          (cond
            ( (null? x) '() )
            ( #t
              (display-num1 (cdr x))
              (display-digit (car x))
            )
          )
        )
      )

      (test-arith
        (lambda ()
          (display-num (list num-mark zsign))
          (newline)
          (display-num (list num-mark psign '_0 '_1))
          (newline)
          (display-num (list num-mark msign '_0 '_2))
          (newline)
        )
      )

When working with signed numbers, both addition and subtraction need to be implemented simultaneously.

First, we define an add procedure that checks the arguments for validity…

      (add
        (lambda (x y)
          (cond
            ( (eq? (car x) num-mark)
              (cond
                ( (eq? (car y) num-mark) (add-num x y) )
                ( #t                     '***undefined*** )
              )
            )
            ( #t '***undefined*** )
          )
        )
      )

Then we check the signs to see if we add, subtract, or simply use one value…

      (add-num
        (lambda (x y)
          (cond
            ( (eq? (car(cdr x)) zsign)        y )
            ( (eq? (car(cdr y)) zsign)        x )
            ( (eq? (car(cdr x)) (car(cdr y))) (add-magnitude (car(cdr x)) (cdr(cdr x)) (cdr(cdr y))) )
            ( (eq? (car(cdr x)) psign)        (sub-magnitude (cdr(cdr x)) (cdr(cdr y))) )
            ( (eq? (car(cdr x)) msign)        (sub-magnitude (cdr(cdr y)) (cdr(cdr x))) )
            ( #t                              '***undefined*** )
          )
        )
      )

When the signs are the same, add-magnitude is passed the common sign and the two magnitudes. If the list lengths are different, the digits in the longer list are added to zero and carry. The commutative property can be used to compact add-mag1, but it was written this way as a template for the sub-mag1 procedure to be shown later.

I won’t bother to show add-digit, which is simply a table implemented with cond expressions. The assembly language version will use a different method of addition. The add-digit procedure takes two digits and a carry, and produces a two-digit list. The second digit is the carry.

      (add-magnitude
        (lambda (sign x y)
          (cons num-mark (cons sign (add-mag1 x y '_0)))
        )
      )

      (add-mag1
        (lambda (x y carry)
          (cond
            ( (null? x)
              (cond
                ( (null? y)
                  (cond
                    ( (eq? carry '_0) '() )
                    ( #t              (list carry) )
                  )
                )
                ( #t
                  (cons
                    (car (add-digit '_0 (car y) carry))
                    (add-mag1
                      '()
                      (cdr y)
                      (car (cdr (add-digit '_0 (car y) carry)))
                    )
                  )
                )
              )
            )
            ( (null? y)
              (cons
                (car (add-digit (car x) '_0 carry))
                (add-mag1
                  (cdr x)
                  '()
                  (car (cdr (add-digit (car x) '_0 carry)))
                )
              )
            )
            ( #t
              (cons
                (car (add-digit (car x) (car y) carry))
                (add-mag1
                  (cdr x)
                  (cdr y)
                  (car (cdr (add-digit (car x) (car y) carry)))
                )
              )
            )
          )
        )
      )

Next, subtraction.

Another Scheme interface to native code

Sunday, July 20th, 2008

As I am used to using arithmetic to compile variables, not having an arithmetic system has slowed me down. I’m not too optimistic about the speed of purely symbolic arithmetic because of the amount of CONSing this system uses.

So, for the interim, I have added an interface to native (machine) code subroutines. Unlike before, the new xeq1 interface passes a list of arguments in the EAX register, rather than the ECX register. As before, a numeric identifier in the form of an octet (equivalent to a byte) is used to select a code address from a dispatch table. This imposes a limit of 256 subroutines. And, as before, the result is returned in the EAX register.

To automatically call the machine code subroutines, the evapply procedure is modified to…

    (evapply
      (lambda (def args)
        (cond
          ( (eq? (first def) mach-mark)   (mach-call (second def) args) )
          ( (eq? (first def) prim-mark)   (prim-call (second def) args) )
          ( (eq? (first def) proc-mark)   (proc-call (cdr(cdr(cdr def))) (second def) (third def) args) )
          ( #t                            '***undefined*** )
        )
      )
    )

    (mach-call
      (lambda (id args)
        (xeq1 id args)
      )
    )

Counting without arithmetic

Wednesday, July 9th, 2008

We would like a compiler to be able to generate unique labels for the assembly code it generates. The little Scheme has no arithmetic, no eqv?, and the numbers that read generates are not unique. A workaround is to substitute digits with symbols containing the digits, and then converting them later to printable form.

Here is a counter using numbers represented as digit lists, with a few tests. Little-endian makes counting relatively simple…

  (letrec
    (
      (counter '(_0))

      (add1
        (lambda (x)
          (cond
            ((eq? (car x) '_0) (cons '_1 (cdr x)))
            ((eq? (car x) '_1) (cons '_2 (cdr x)))
            ((eq? (car x) '_2) (cons '_3 (cdr x)))
            ((eq? (car x) '_3) (cons '_4 (cdr x)))
            ((eq? (car x) '_4) (cons '_5 (cdr x)))
            ((eq? (car x) '_5) (cons '_6 (cdr x)))
            ((eq? (car x) '_6) (cons '_7 (cdr x)))
            ((eq? (car x) '_7) (cons '_8 (cdr x)))
            ((eq? (car x) '_8) (cons '_9 (cdr x)))
            ((eq? (car x) '_9) (cons '_0 (cond
                                           ( (null? (cdr x))  '(_1) )
                                           ( #t               (add1 (cdr x)) )
                                         )
                               )
            )
          )
        )
      )

      (reverse1
        (lambda (old new)
          (cond
            ( (null? old) new )
            ( #t          (reverse1 (cdr old) (cons (car old) new)) )
          )
        )
      )

      (reverse
        (lambda (x)
          (reverse1 x '())
        )
      )

      (genlabel
        (lambda ()
          (set! counter (add1 counter))
          (reverse counter)
        )
      )

    )

    (newline)
    (display (genlabel))
    (newline)
    (display (genlabel))
    (newline)
    (set! counter '(_9))
    (display (genlabel))
    (newline)
    (set! counter '(_9 _9 _3))
    (display (genlabel))
  )

Assembly language for Scheme

Thursday, July 3rd, 2008

It didn’t take much time to add variable length argument lists to the base interpreter.

So now, an assembly language for the little Scheme. It looks pretty much like very linear Common Lisp prog code…

          (mov     (mem ecx*4 56) 65)
          m_push
          (mov     ecx eax)
          (mov     edx HeapBase)
          (mov     edx (edx offsetEVALSTACK offsetCDR))
          (call    m_cons1)
          (mov     edx HeapBase)
          (mov     (edx offsetEVALSTACK offsetCDR) eax)
          (ret)

Until arithmetic is provided, we can cheat and pass all the hard work to MASM (I’m already using it for the base interpreter). The translation of the above is…

mov [mem+ecx*4+56],65
m_push:
mov ecx,eax
mov edx,HeapBase
mov edx,[edx+offsetEVALSTACK+offsetCDR]
call m_cons1
mov edx,HeapBase
mov [edx+offsetEVALSTACK+offsetCDR],eax
ret

The for-each iterator makes the main part fairly simple…

  (letrec
    (
      (code
       '(
          m_car
          (mov     eax (eax offsetCAR))
          (ret)
          ; --- assembly code omitted ---
        )
      )
    )

    (open-output (cdr 'SchCode.inc))
    (for-each translate code)
    (close-output)
  )

The translate procedure checks if the list item is a label. If so, it writes the label to the output file and adds the colon character. If it’s not a label, the item is assumed to be a list, and it expects the first item will be the opcode symbol. It then accepts up to two operands, adding a space and a comma character if necessary. Normally I would use a literal, rather than thinking up a name for the characters. But rather than naming them, the characters are generated in-line with integer->octet. The Windows standard CR-LF line ending is also added…

      (translate
        (lambda (x)
          (cond
            ( (symbol? x) (write-sym x) (write-octet (integer->octet 58)) )
            ( #t
              (write-sym (first x))
              (cond
                ( (null? (cdr x)) '() )
                ( #t
                  (write-octet (integer->octet 32))
                  (write-operand (second x))
                  (cond
                    ( (null? (cdr(cdr x))) '() )
                    ( #t
                      (write-octet (integer->octet 44))
                      (write-operand (third x))
                    )
                  )
                )
              )
            )
          )
          (write-octet (integer->octet 13))
          (write-octet (integer->octet 10))
        )
      )
    )

The write-operand procedure checks for numbers or symbols. If neither, it assumes a list that will end up as a memory reference in MASM/Intel format. The parentheses (which don’t exist as data in the code lists) are replaced with square brackets. The plus sign is added between list items…

      (write-operand
        (lambda (x)
          (cond
            ( (number? x) (write-number x) )
            ( (symbol? x) (write-sym x) )
            ( #t
              (write-octet (integer->octet 91))
              (write-sym (car x))
              (cond
                ( (null? (cdr x)) '() )
                ( #t              (for-each write-plus-term (cdr x)) )
              )
              (write-octet (integer->octet 93))
            )
          )
        )
      )

      (write-plus-term
        (lambda (x)
          (write-octet (integer->octet 43))
          (cond
            ( (number? x) (write-number x) )
            ( #t          (write-sym x) )
          )
        )
      )

The other procedures inspect the internal structure of symbols and numbers in order to generate the octets that are sent to the output file.