Skip to content

Eval

Jump to bottom
agreppin edited this page Sep 29, 2021 · 10 revisions

undefined behavior

What is stated as undefined in John McCarthy's paper is left as is, period.

(CAR NIL)
... the result is undefined ...

(COND (NIL NIL))
... may never decide what to answer ...

It is the user responsibility to feed valid input to the interpreter. Our sectorlisp is not able to emit errors or check for border cases.

ATOM and CONS tagging

case ATOM tag is 0

#define ATOM 0
#define CONS 1
#define OBJECT(t, v)    (((v)<<1)|(t))
#define VALUE(x) ((x) >> 1)
#define NIL  0

Testing for zero or NULL value in C/C++ yields shorter machine code

  test %ax,%ax
  jnz ...

than comparing explicitly with the zero value

  cmp $0, %ax
  jne ...

the compiler generated code to get the value of Cdr(di) is

Car:
  and $-2,%di
  mov (%di),%ax
  ret

but, as we are now quite sure that we never pass an ATOM to Car() or Cdr() this can be simplified as

Car:
  dec %di
  mov (%di),%ax
  ret

It there a relation to the "content of the decrement register" on an IBM 704 ? Who knows ?

case ATOM tag is 1

#define ATOM 1
#define CONS 0
...
#define NIL  (ATOM | 0)

In this case, every CONS cell is the address of that cell. The code becomes quite easy to understand.

Cadr:
  mov 2(%di),%di
  mov (%di),%ax
  ret

Comparing for against the NIL value is now required. The code size gain overall is worth the effort.

Eval() v1

Bind()

The code generated by the compiler with -Os and the realify.sh wrapper is not well optimized for size. By manually reordering the evaluation of the statements we can gain some precious bits. In C/C++, the evaluation order of the arguments to a function is unspecified, I don't know for LISP.

WORD Bind(WORD v, WORD a, WORD e) { // evlis + pair w/ dot notation
  if (v == NIL)
     return e;
  WORD t1 = Eval(Car(a), e);
  WORD t2 = Cons(Car(v), t1);
  WORD t3 = Bind(Cdr(v), Cdr(a), e);
  return Cons(t2, t3);
}

can be transcribed as

Bind:                   # Bind(v:di,a:si,e:dx):ax
  cmp     $NIL,%di
  je      1f
  push    2(%di)        # 1 save Cdr(v)
  push    2(%si)        # 2 save Cdr(a)
  push    %dx           # 3 save e
  push    (%di)         # 4 save Car(v)
  mov     (%si),%ax     # ax = Car(a)
  xchg    %dx,%si
  call    Eval
  xchg    %ax,%si
  pop     %di           # 4 restore di = Car(v)
  call    Cons
  pop     %dx           # 3 restore e
  pop     %si           # 2 restore Cdr(a)
  pop     %di           # 1 restore Cdr(v)
  push    %ax           # 5 save
  call    Bind
  xchg    %ax,%si
  pop     %di           # 5 restore
  jmp     Cons
1:xchg    %dx,%ax
  ret

Eval() v2

By searching a way to save more bytes, I found this page: What is the most minimal implementation of Lisp available? where pbewig commented:

The canonical implementation of Lisp is on page 13 of John McCarthy's book; everything else is a library function.

This refers to the LISP 1.5 Programmer's Manual. This is the source for the new Eval() function, with some adaptations like in Assoc() ...

It is possible to run the LISP 1.5 code with the SIMH simulator for the IBM 7094 on your PC.

Clone this wiki locally