SECD:   A reduced version.
1 Introduction
2 Instruction Set
INT_  CONST
ADD
SUB
FUN
RETURN
APPLY
IF0
7.1

SECD: A reduced version.

Gaspar Ricci

 #lang secd package: secd

1 Introduction

This is an implementation of a compiler for a very small subset of the SECD language. The programs written in this language will be compiled to ARM Assembler. The resulting program will run the instructions and print the result in the standard output.

As an example. If the source SECD program is:

#lang secd

(

 (INT_CONST 56)

 (FUN (IF0 ((FUN (INT_CONST 4) (ADD) (RETURN)) (INT_CONST 3) (APPLY))

           ((FUN (INT_CONST 8) (ADD) (RETURN)) (INT_CONST 6) (APPLY)))

      (RETURN))

 (INT_CONST 0)

 (APPLY)

 (ADD))

The resulting ARM Assembler program will be:

.data

        fstr: .asciz "%d\n"

 

.text

.global main

.extern printf

 

fun0:

        stmfd sp!, {fp, ip, lr}

        mov fp, sp

 

        stmfd sp!, {r0}

 

        ldr r0, =4

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r1}

        add r0, r1

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0}

 

        mov sp, fp

        ldmfd sp!, {fp, ip, pc}

 

fun1:

        stmfd sp!, {fp, ip, lr}

        mov fp, sp

 

        stmfd sp!, {r0}

 

        ldr r0, =8

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r1}

        add r0, r1

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0}

 

        mov sp, fp

        ldmfd sp!, {fp, ip, pc}

 

fun2:

        stmfd sp!, {fp, ip, lr}

        mov fp, sp

 

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0}

        tst r0, r0

        bne ifnz0

 

        ldr r0, =fun0

        stmfd sp!, {r0}

 

        ldr r0, =3

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r7}

        blx r7

        stmfd sp!, {r0}

 

        b endifz0

 

        ifnz0:

 

        ldr r0, =fun1

        stmfd sp!, {r0}

 

        ldr r0, =6

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r7}

        blx r7

        stmfd sp!, {r0}

 

        endifz0:

 

        ldmfd sp!, {r0}

 

        mov sp, fp

        ldmfd sp!, {fp, ip, pc}

 

main:

 

        stmfd sp!, {fp, ip, lr}

        mov fp, sp

 

        ldr r0, =56

        stmfd sp!, {r0}

 

        ldr r0, =fun2

        stmfd sp!, {r0}

 

        ldr r0, =0

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r7}

        blx r7

        stmfd sp!, {r0}

 

        ldmfd sp!, {r0, r1}

        add r0, r1

        stmfd sp!, {r0}

 

        ldmfd sp!, {r1}

        ldr r0, =fstr

        bl printf

 

        mov sp, fp

        ldmfd sp!, {fp, ip, pc}

Assuming that the output source file is called program.s, programs produced by the SECD language can be compiled using the following commands:

$ gcc -c program.s -o program.o

$ gcc program.o -o program

If you compile and run the example above, the result will be

$ ./program

63

2 Instruction Set

As explained in the introduction, this implementation provides only a small subset of the instructions available in the SECD language. Moreover, the names of the instructions differ from the real ones. Only the following instructions are available in the current release. This instruction set will be expanded in the near future.

secd-instruction

(INT_CONST value)  void

  value : (integer?)
Pushes value to the current stack, value must be an integer.

secd-instruction

(ADD)  void

Pops the top two values off the current stack, adds them and pushes the result back to the current stack.

secd-instruction

(SUB)  void

Pops the top two values in the current stack, subtracts them and pushes the result back to the current stack. Note: If first is the element at the top of the current stack before executing (SUB) and second is the following element, then the subtraction performed is first - second.

secd-instruction

(FUN instruction ... return)  void

  instruction : secd-instruction?
  return : secd-return?
Defines a function with zero or more secd-instructions followed by a (RETURN) instruction. This means that the smallest possible function definition is (FUN (RETURN)) which, when executed, returns the received argument. Note: The instructions of a function are executed on an independent stack. In other words, a function starts its execution with a stack containing a single value: the received argument, and once it returns, its stack is completely discarded. This follows the principle of functional programming, which is the idea behind the abstract SECD machine. Once the function is defined, a pointer to it is pushed into the current stack.

secd-instruction

(RETURN)  void

Pops the top value off the function’s stack and pushes it into the stack of the function’s caller.

secd-instruction

(APPLY)  void

Pops the top two values in the current stack, the first one is the argument that is going to be passed to the function pointed by the second popped element.

secd-instruction

(IF0 trueInstrs falseInstrs)  void

  trueInstrs : secd-instruction-list?
  falseInstrs : secd-instruction-list?
Pops the top value in the current stack. If it is zero, the instructions in trueInstrs are executed. Otherwise, the instructions in falseInstrs are executed.