lispstrack.lisp

   1 (defun ensure-list (x)
   2   (if (listp x)
   3       x
   4       (list x)))
   5
   6 (defun !reduce (func list initial)
   7   (if (null list)
   8       initial
   9       (!reduce func
  10                (cdr list)
  11                (funcall func initial (car list)))))
  12
  13 ;;; Utils
  14
  15 #+common-lisp
  16 (progn
  17   (defmacro while (condition &body body)
  18     `(do ()
  19          ((not ,condition))
  20        ,@body))
  21
  22   (defun concat-two (s1 s2)
  23     (concatenate 'string s1 s2))
  24
  25   (defun setcar (cons new)
  26     (setf (car cons) new))
  27   (defun setcdr (cons new)
  28     (setf (cdr cons) new)))
  29
  30 (defvar *newline* (string (code-char 10)))
  31
  32 (defun concat (&rest strs)
  33   (!reduce (lambda (s1 s2) (concat-two s1 s2))
  34            strs
  35            ""))
  36
  37 ;;; Concatenate a list of strings, with a separator
  38 (defun join (list separator)
  39   (cond
  40     ((null list)
  41      "")
  42     ((null (cdr list))
  43      (car list))
  44     (t
  45      (concat (car list)
  46              separator
  47              (join (cdr list) separator)))))
  48
  49 (defun join-trailing (list separator)
  50   (cond
  51     ((null list)
  52      "")
  53     ((null (car list))
  54      (join-trailing (cdr list) separator))
  55     (t
  56      (concat (car list) separator (join-trailing (cdr list) separator)))))
  57
  58 (defun integer-to-string (x)
  59   (if (zerop x)
  60       "0"
  61       (let ((digits nil))
  62         (while (not (= x 0))
  63           (push (mod x 10) digits)
  64           (setq x (truncate x 10)))
  65         (join (mapcar (lambda (d) (string (char "0123456789" d)))
  66                       digits)
  67               ""))))
  68
  69 ;;;; Reader
  70
  71 ;;; It is a basic Lisp reader. It does not use advanced stuff
  72 ;;; intentionally, because we want to use it to bootstrap a simple
  73 ;;; Lisp. The main entry point is the function `ls-read', which
  74 ;;; accepts a strings as argument and return the Lisp expression.
  75 (defun make-string-stream (string)
  76   (cons string 0))
  77
  78 (defun %peek-char (stream)
  79   (and (< (cdr stream) (length (car stream)))
  80        (char (car stream) (cdr stream))))
  81
  82 (defun %read-char (stream)
  83   (and (< (cdr stream) (length (car stream)))
  84        (prog1 (char (car stream) (cdr stream))
  85          (setcdr stream (1+ (cdr stream))))))
  86
  87 (defun whitespacep (ch)
  88   (or (char= ch #\space) (char= ch #\newline) (char= ch #\tab)))
  89
  90 (defun skip-whitespaces (stream)
  91   (let (ch)
  92     (setq ch (%peek-char stream))
  93     (while (and ch (whitespacep ch))
  94       (%read-char stream)
  95       (setq ch (%peek-char stream)))))
  96
  97 (defun terminalp (ch)
  98   (or (null ch) (whitespacep ch) (char= #\) ch) (char= #\( ch)))
  99
 100 (defun read-until (stream func)
 101   (let ((string "")
 102         (ch))
 103     (setq ch (%peek-char stream))
 104     (while (not (funcall func ch))
 105       (setq string (concat string (string ch)))
 106       (%read-char stream)
 107       (setq ch (%peek-char stream)))
 108     string))
 109
 110 (defun skip-whitespaces-and-comments (stream)
 111   (let (ch)
 112     (skip-whitespaces stream)
 113     (setq ch (%peek-char stream))
 114     (while (and ch (char= ch #\;))
 115       (read-until stream (lambda (x) (char= x #\newline)))
 116       (skip-whitespaces stream)
 117       (setq ch (%peek-char stream)))))
 118
 119 (defun %read-list (stream)
 120   (skip-whitespaces-and-comments stream)
 121   (let ((ch (%peek-char stream)))
 122     (cond
 123       ((char= ch #\))
 124        (%read-char stream)
 125        nil)
 126       ((char= ch #\.)
 127        (%read-char stream)
 128        (skip-whitespaces-and-comments stream)
 129        (prog1 (ls-read stream)
 130          (unless (char= (%read-char stream) #\))
 131            (error "')' was expected."))))
 132       (t
 133        (cons (ls-read stream) (%read-list stream))))))
 134
 135 (defun read-string (stream)
 136   (let ((string "")
 137         (ch nil))
 138     (setq ch (%read-char stream))
 139     (while (not (char= ch #\"))
 140       (when (char= ch #\\)
 141         (setq ch (%read-char stream)))
 142       (setq string (concat string (string ch)))
 143       (setq ch (%read-char stream)))
 144     string))
 145
 146 (defvar *eof* (make-symbol "EOF"))
 147 (defun ls-read (stream)
 148   (skip-whitespaces-and-comments stream)
 149   (let ((ch (%peek-char stream)))
 150     (cond
 151       ((null ch)
 152        *eof*)
 153       ((char= ch #\()
 154        (%read-char stream)
 155        (%read-list stream))
 156       ((char= ch #\')
 157        (%read-char stream)
 158        (list 'quote (ls-read stream)))
 159       ((char= ch #\`)
 160        (%read-char stream)
 161        (list 'backquote (ls-read stream)))
 162       ((char= ch #\")
 163        (%read-char stream)
 164        (read-string stream))
 165       ((char= ch #\,)
 166        (%read-char stream)
 167        (if (eql (%peek-char stream) #\@)
 168            (progn (%read-char stream) (list 'unquote-splicing (ls-read stream)))
 169            (list 'unquote (ls-read stream))))
 170       ((char= ch #\#)
 171        (%read-char stream)
 172        (ecase (%read-char stream)
 173          (#\'
 174           (list 'function (ls-read stream)))
 175          (#\\
 176           (let ((cname
 177                  (concat (string (%read-char stream))
 178                          (read-until stream #'terminalp))))
 179             (cond
 180               ((string= cname "space") (char-code #\space))
 181               ((string= cname "newline") (char-code #\newline))
 182               (t (char-code (char cname 0))))))
 183          (#\+
 184           (let ((feature (read-until stream #'terminalp)))
 185             (cond
 186               ((string= feature "common-lisp")
 187                (ls-read stream)         ;ignore
 188                (ls-read stream))
 189               ((string= feature "lispstrack")
 190                (ls-read stream))
 191               (t
 192                (error "Unknown reader form.")))))))
 193       (t
 194        (let ((string (read-until stream #'terminalp)))
 195          (if (every #'digit-char-p string)
 196              (parse-integer string)
 197              (intern (string-upcase string))))))))
 198
 199 (defun ls-read-from-string (string)
 200   (ls-read (make-string-stream string)))
 201
 202
 203 ;;;; Compiler
 204
 205 (defvar *compilation-unit-checks* '())
 206
 207 (defvar *env* '())
 208 (defvar *fenv* '())
 209
 210 (defun make-binding (name type js declared)
 211   (list name type js declared))
 212
 213 (defun binding-name (b) (first b))
 214 (defun binding-type (b) (second b))
 215 (defun binding-translation (b) (third b))
 216 (defun binding-declared (b)
 217   (and b (fourth b)))
 218 (defun mark-binding-as-declared (b)
 219   (setcar (cdddr b) t))
 220
 221 (let ((counter 0))
 222   (defun gvarname (symbol)
 223     (concat "v" (integer-to-string (incf counter))))
 224
 225   (defun lookup-variable (symbol env)
 226     (or (assoc symbol env)
 227         (assoc symbol *env*)
 228         (let ((name (symbol-name symbol))
 229               (binding (make-binding symbol 'variable (gvarname symbol) nil)))
 230           (push binding *env*)
 231           (push (lambda ()
 232                   (unless (binding-declared (assoc symbol *env*))
 233                     (error (concat "Undefined variable `" name "'"))))
 234                 *compilation-unit-checks*)
 235           binding)))
 236
 237   (defun lookup-variable-translation (symbol env)
 238     (binding-translation (lookup-variable symbol env)))
 239
 240   (defun extend-local-env (args env)
 241     (append (mapcar (lambda (symbol)
 242                       (make-binding symbol 'variable (gvarname symbol) t))
 243                     args)
 244             env)))
 245
 246 (let ((counter 0))
 247   (defun lookup-function (symbol env)
 248     (or (assoc symbol env)
 249         (assoc symbol *fenv*)
 250         (let ((name (symbol-name symbol))
 251               (binding
 252                (make-binding symbol
 253                              'function
 254                              (concat "f" (integer-to-string (incf counter)))
 255                              nil)))
 256           (push binding *fenv*)
 257           (push (lambda ()
 258                   (unless (binding-declared (assoc symbol *fenv*))
 259                     (error (concat "Undefined function `" name "'"))))
 260                 *compilation-unit-checks*)
 261           binding)))
 262
 263   (defun lookup-function-translation (symbol env)
 264     (binding-translation (lookup-function symbol env))))
 265
 266
 267 (defvar *toplevel-compilations* nil)
 268
 269 (defun %compile-defvar (name)
 270   (let ((b (lookup-variable name *env*)))
 271     (mark-binding-as-declared b)
 272     (push (concat "var " (binding-translation b)) *toplevel-compilations*)))
 273
 274 (defun %compile-defun (name)
 275   (let ((b (lookup-function name *env*)))
 276     (mark-binding-as-declared b)
 277     (push (concat "var " (binding-translation b)) *toplevel-compilations*)))
 278
 279 (defun %compile-defmacro (name lambda)
 280   (push (make-binding name 'macro lambda t) *fenv*))
 281
 282
 283 (defvar *compilations* nil)
 284
 285 (defun ls-compile-block (sexps env fenv)
 286   (join-trailing
 287    (remove nil (mapcar (lambda (x)
 288                          (ls-compile x env fenv))
 289                        sexps))
 290                  ";
 291 "))
 292 (defmacro define-compilation (name args &rest body)
 293   ;; Creates a new primitive `name' with parameters args and
 294   ;; @body. The body can access to the local environment through the
 295   ;; variable ENV.
 296   `(push (list ',name (lambda (env fenv ,@args) ,@body))
 297          *compilations*))
 298
 299 (define-compilation if (condition true false)
 300   (concat "("
 301           (ls-compile condition env fenv)
 302           " ? "
 303           (ls-compile true env fenv)
 304           " : "
 305           (ls-compile false env fenv)
 306           ")"))
 307
 308 ;;; Return the required args of a lambda list
 309 (defun lambda-list-required-argument (lambda-list)
 310   (if (or (null lambda-list) (eq (car lambda-list) '&rest))
 311       nil
 312       (cons (car lambda-list) (lambda-list-required-argument (cdr lambda-list)))))
 313
 314 (defun lambda-list-rest-argument (lambda-list)
 315   (second (member '&rest lambda-list)))
 316
 317 (define-compilation lambda (lambda-list &rest body)
 318   (let ((required-arguments (lambda-list-required-argument lambda-list))
 319         (rest-argument (lambda-list-rest-argument lambda-list)))
 320     (let ((new-env (extend-local-env
 321                     (append (and rest-argument (list rest-argument))
 322                             required-arguments)
 323                     env)))
 324       (concat "(function ("
 325               (join (mapcar (lambda (x)
 326                               (lookup-variable-translation x new-env))
 327                             required-arguments)
 328                     ",")
 329               "){"
 330               *newline*
 331               (if rest-argument
 332                   (let ((js!rest (lookup-variable-translation rest-argument new-env)))
 333                     (concat "var " js!rest ";" *newline*
 334                             "for (var i = arguments.length-1; i>="
 335                             (integer-to-string (length required-arguments))
 336                             "; i--)" *newline*
 337                             js!rest " = "
 338                             "{car: arguments[i], cdr: " js!rest "};"
 339                             *newline*))
 340                   "")
 341               (concat (ls-compile-block (butlast body) new-env fenv)
 342                       "return " (ls-compile (car (last body)) new-env fenv) ";")
 343               *newline*
 344               "})"))))
 345
 346 (define-compilation fsetq (var val)
 347   (concat (lookup-function-translation var fenv)
 348           " = "
 349           (ls-compile val env fenv)))
 350
 351 (define-compilation setq (var val)
 352   (concat (lookup-variable-translation var env)
 353           " = "
 354            (ls-compile val env fenv)))
 355
 356 ;;; Literals
 357
 358 (defun literal->js (sexp)
 359   (cond
 360     ((null sexp) "false")
 361     ((integerp sexp) (integer-to-string sexp))
 362     ((stringp sexp) (concat "\"" sexp "\""))
 363     ((symbolp sexp) (concat "{name: \"" (symbol-name sexp) "\"}"))
 364     ((consp sexp) (concat "{car: "
 365                           (literal->js (car sexp))
 366                           ", cdr: "
 367                           (literal->js (cdr sexp)) "}"))))
 368
 369 (let ((counter 0))
 370   (defun literal (form)
 371     (if (null form)
 372         (literal->js form)
 373         (let ((var (concat "l" (integer-to-string (incf counter)))))
 374           (push (concat "var " var " = " (literal->js form)) *toplevel-compilations*)
 375           var))))
 376
 377 (define-compilation quote (sexp)
 378   (literal sexp))
 379
 380 (define-compilation debug (form)
 381   (concat "console.log(" (ls-compile form env fenv) ")"))
 382
 383 (define-compilation while (pred &rest body)
 384   (concat "(function(){ while("
 385           (ls-compile pred env fenv)
 386           "){"
 387           (ls-compile-block body env fenv)
 388           "}})()"))
 389
 390 (define-compilation function (x)
 391   (cond
 392     ((and (listp x) (eq (car x) 'lambda))
 393      (ls-compile x env fenv))
 394     ((symbolp x)
 395      (lookup-function-translation x fenv))))
 396
 397 #+common-lisp
 398 (defmacro eval-when-compile (&body body)
 399   `(eval-when (:compile-toplevel :load-toplevel :execute)
 400      ,@body))
 401
 402 (define-compilation eval-when-compile (&rest body)
 403   (eval (cons 'progn body))
 404   nil)
 405
 406 (defmacro define-transformation (name args form)
 407   `(define-compilation ,name ,args
 408      (ls-compile ,form env fenv)))
 409
 410 (define-transformation progn (&rest body)
 411   `((lambda () ,@body)))
 412
 413 (define-transformation let (bindings &rest body)
 414   (let ((bindings (mapcar #'ensure-list bindings)))
 415     `((lambda ,(mapcar 'car bindings) ,@body)
 416       ,@(mapcar 'cadr bindings))))
 417
 418 ;;; A little backquote implementation without optimizations of any
 419 ;;; kind for lispstrack.
 420 (defun backquote-expand-1 (form)
 421   (cond
 422     ((symbolp form)
 423      (list 'quote form))
 424     ((atom form)
 425      form)
 426     ((eq (car form) 'unquote)
 427      (car form))
 428     ((eq (car form) 'backquote)
 429      (backquote-expand-1 (backquote-expand-1 (cadr form))))
 430     (t
 431      (cons 'append
 432            (mapcar (lambda (s)
 433                      (cond
 434                        ((and (listp s) (eq (car s) 'unquote))
 435                         (list 'list (cadr s)))
 436                        ((and (listp s) (eq (car s) 'unquote-splicing))
 437                         (cadr s))
 438                        (t
 439                         (list 'list (backquote-expand-1 s)))))
 440                    form)))))
 441
 442 (defun backquote-expand (form)
 443   (if (and (listp form) (eq (car form) 'backquote))
 444       (backquote-expand-1 (cadr form))
 445       form))
 446
 447 (defmacro backquote (form)
 448   (backquote-expand-1 form))
 449
 450 (define-transformation backquote (form)
 451   (backquote-expand-1 form))
 452
 453 ;;; Primitives
 454
 455 (define-compilation + (x y)
 456   (concat "((" (ls-compile x env fenv) ") + (" (ls-compile y env fenv) "))"))
 457
 458 (define-compilation - (x y)
 459   (concat "((" (ls-compile x env fenv) ") - (" (ls-compile y env fenv) "))"))
 460
 461 (define-compilation * (x y)
 462   (concat "((" (ls-compile x env fenv) ") * (" (ls-compile y env fenv) "))"))
 463
 464 (define-compilation / (x y)
 465   (concat "((" (ls-compile x env fenv) ") / (" (ls-compile y env fenv) "))"))
 466
 467 (define-compilation < (x y)
 468   (concat "((" (ls-compile x env fenv) ") < (" (ls-compile y env fenv) "))"))
 469
 470 (define-compilation = (x y)
 471   (concat "((" (ls-compile x env fenv) ") == (" (ls-compile y env fenv) "))"))
 472
 473 (define-compilation numberp (x)
 474   (concat "(typeof (" (ls-compile x env fenv) ") == \"number\")"))
 475
 476
 477 (define-compilation mod (x y)
 478   (concat "((" (ls-compile x env fenv) ") % (" (ls-compile y env fenv) "))"))
 479
 480 (define-compilation floor (x)
 481   (concat "(Math.floor(" (ls-compile x env fenv) "))"))
 482
 483 (define-compilation null (x)
 484   (concat "(" (ls-compile x env fenv) "== false)"))
 485
 486 (define-compilation cons (x y)
 487   (concat "{car: " (ls-compile x env fenv) ", cdr: " (ls-compile y env fenv) "}"))
 488
 489 (define-compilation consp (x)
 490   (concat "('car' in " (ls-compile x env fenv) ")"))
 491
 492
 493 (define-compilation car (x)
 494   (concat "(" (ls-compile x env fenv) ").car"))
 495
 496 (define-compilation cdr (x)
 497   (concat "(" (ls-compile x env fenv) ").cdr"))
 498
 499 (define-compilation setcar (x new)
 500   (concat "((" (ls-compile x env fenv) ").car = " (ls-compile new env fenv) ")"))
 501
 502 (define-compilation setcdr (x new)
 503   (concat "((" (ls-compile x env fenv) ").cdr = " (ls-compile new env fenv) ")"))
 504
 505 (define-compilation symbolp (x)
 506   (concat "('name' in " (ls-compile x env fenv) ")"))
 507
 508 (define-compilation make-symbol (name)
 509   (concat "{name: " (ls-compile name env fenv) "}"))
 510
 511 (define-compilation symbol-name (x)
 512   (concat "(" (ls-compile x env fenv) ").name"))
 513
 514 (define-compilation eq (x y)
 515   (concat "(" (ls-compile x env fenv) " === " (ls-compile y env fenv) ")"))
 516
 517 (define-compilation equal (x y)
 518   (concat "(" (ls-compile x env fenv) " == " (ls-compile y env fenv) ")"))
 519
 520 (define-compilation string (x)
 521   (concat "String.fromCharCode(" (ls-compile x env fenv) ")"))
 522
 523 (define-compilation stringp (x)
 524   (concat "(typeof(" (ls-compile x env fenv) ") == \"string\")"))
 525
 526 (define-compilation string-upcase (x)
 527   (concat "(" (ls-compile x env fenv) ").toUpperCase()"))
 528
 529 (define-compilation string-length (x)
 530   (concat "(" (ls-compile x env fenv) ").length"))
 531
 532 (define-compilation char (string index)
 533   (concat "("
 534           (ls-compile string env fenv)
 535           ").charCodeAt("
 536           (ls-compile index env fenv)
 537           ")"))
 538
 539 (define-compilation concat-two (string1 string2)
 540   (concat "("
 541           (ls-compile string1 env fenv)
 542           ").concat("
 543           (ls-compile string2 env fenv)
 544           ")"))
 545
 546 (define-compilation funcall (func &rest args)
 547   (concat "("
 548           (ls-compile func env fenv)
 549           ")("
 550           (join (mapcar (lambda (x)
 551                           (ls-compile x env fenv))
 552                         args)
 553                 ", ")
 554           ")"))
 555
 556 (define-transformation apply (func &rest args)
 557   (if (null args)
 558       (concat "(" (ls-compile func env fenv) ")()")
 559       (let ((args (butlast args))
 560             (last (car (last args))))
 561         (concat "function(){" *newline*
 562                 "var f = " (ls-compile func env fenv) ";" *newline*
 563                 "var args = [" (join (mapcar (lambda (x)
 564                                                (ls-compile x env fenv))
 565                                              args)
 566                                      ", ")
 567                 "];" *newline*
 568                 "var tail = (" (ls-compile last env fenv) ");"
 569                 "while (tail != false){" *newline*
 570                 "    args.push(tail[0]);" *newline*
 571                 "    args = args.slice(1);"
 572                 "}" *newline*
 573                 "return f.apply(this, args);" *newline*
 574                 "}" *newline*))))
 575
 576 (define-compilation js-eval (string)
 577   (concat "eval(" (ls-compile string env fenv)  ")"))
 578
 579
 580 (define-compilation error (string)
 581   (concat "(function (){ throw " (ls-compile string env fenv) ";" "return 0;})()"))
 582
 583 (define-compilation new ()
 584   "{}")
 585
 586 (define-compilation get (object key)
 587   (concat "(" (ls-compile object env fenv) ")[" (ls-compile key env fenv) "]"))
 588
 589 (define-compilation set (object key value)
 590   (concat "(("
 591           (ls-compile object env fenv)
 592           ")["
 593           (ls-compile key env fenv) "]"
 594           " = " (ls-compile value env fenv) ")"))
 595
 596 (defun macrop (x)
 597   (and (symbolp x) (eq (binding-type (lookup-function x *fenv*)) 'macro)))
 598
 599 (defun ls-macroexpand-1 (form &optional env fenv)
 600   (when (macrop (car form))
 601     (let ((binding (lookup-function (car form) *env*)))
 602       (if (eq (binding-type binding) 'macro)
 603           (apply (eval (binding-translation binding)) (cdr form))
 604           form))))
 605
 606 (defun compile-funcall (function args env fenv)
 607   (cond
 608     ((symbolp function)
 609      (concat (lookup-function-translation function fenv)
 610              "("
 611              (join (mapcar (lambda (x) (ls-compile x env fenv)) args)
 612                    ", ")
 613              ")"))
 614     ((and (listp function) (eq (car function) 'lambda))
 615      (concat "(" (ls-compile function env fenv) ")("
 616              (join (mapcar (lambda (x) (ls-compile x env fenv)) args)
 617                    ", ")
 618              ")"))
 619     (t
 620      (error (concat "Invalid function designator " (symbol-name function))))))
 621
 622 (defun ls-compile (sexp &optional env fenv)
 623   (cond
 624     ((symbolp sexp) (lookup-variable-translation sexp env))
 625     ((integerp sexp) (integer-to-string sexp))
 626     ((stringp sexp) (concat "\"" sexp "\""))
 627     ((listp sexp)
 628      (if (assoc (car sexp) *compilations*)
 629          (let ((comp (second (assoc (car sexp) *compilations*))))
 630            (apply comp env fenv (cdr sexp)))
 631          (if (macrop (car sexp))
 632              (ls-compile (ls-macroexpand-1 sexp env fenv) env fenv)
 633              (compile-funcall (car sexp) (cdr sexp) env fenv))))))
 634
 635 (defun ls-compile-toplevel (sexp)
 636   (setq *toplevel-compilations* nil)
 637   (let ((code (ls-compile sexp)))
 638     (prog1
 639         (concat (join (mapcar (lambda (x) (concat x ";" *newline*))
 640                               *toplevel-compilations*)
 641                       "")
 642                 code)
 643       (setq *toplevel-compilations* nil))))
 644
 645 #+common-lisp
 646 (progn
 647   (defun read-whole-file (filename)
 648     (with-open-file (in filename)
 649       (let ((seq (make-array (file-length in) :element-type 'character)))
 650         (read-sequence seq in)
 651         seq)))
 652
 653   (defun ls-compile-file (filename output)
 654     (setq *env* nil *fenv* nil)
 655     (setq *compilation-unit-checks* nil)
 656     (with-open-file (out output :direction :output :if-exists :supersede)
 657       (let* ((source (read-whole-file filename))
 658              (in (make-string-stream source)))
 659         (loop
 660            for x = (ls-read in)
 661            until (eq x *eof*)
 662            for compilation = (ls-compile-toplevel x)
 663            when (plusp (length compilation))
 664            do (write-line (concat compilation "; ") out))
 665         (dolist (check *compilation-unit-checks*)
 666           (funcall check))
 667         (setq *compilation-unit-checks* nil))))
 668
 669   (defun bootstrap ()
 670     (ls-compile-file "lispstrack.lisp" "lispstrack.js")))