X-Git-Url: https://thelambdalab.xyz/gitweb/index.cgi?a=blobdiff_plain;f=src%2Fscheme.4th;h=934775080aa276c352d852a1b9b525904bf28442;hb=ed0aaed61b10e03e5f064404f506eaa73e50c87d;hp=4d5e33bc9c1c0ff04a93bddf3d0cf6def3299a5a;hpb=346e7741d328a4521e8673f1c0418d05d59a4439;p=scheme.forth.jl.git diff --git a/src/scheme.4th b/src/scheme.4th index 4d5e33b..9347750 100644 --- a/src/scheme.4th +++ b/src/scheme.4th @@ -39,6 +39,7 @@ make-type pair-type make-type symbol-type make-type primitive-proc-type make-type compound-proc-type +make-type continuation-type make-type port-type : istype? ( obj type -- obj bool ) over = ; @@ -62,7 +63,7 @@ variable nextexception make-exception recoverable-exception make-exception unrecoverable-exception -: throw reset-term throw ; +: throw reset-term cr throw ; \ }}} @@ -90,7 +91,7 @@ variable nextfree nextfree ! nextfree @ scheme-memsize >= if - collect-garbage + collect-garbage then nextfree @ scheme-memsize >= if @@ -132,6 +133,10 @@ variable nextfree cdr-cells + ! ; +variable object-stack-base +: init-object-stack-base + depth object-stack-base ! ; + : nil 0 nil-type ; : nil? nil-type istype? ; @@ -402,6 +407,9 @@ variable read-line-buffer-offset : make-frame ( vars vals -- frame ) cons ; +: add-frame-to-env ( frame env -- env ) + cons ; + : frame-vars ( frame -- vars ) car ; @@ -416,99 +424,90 @@ variable read-line-buffer-offset ; : extend-env ( vars vals env -- env ) - >R >R - make-frame - R> R> - cons + -2rot make-frame + 2swap add-frame-to-env ; -objvar vars -objvar vals - -: get-vars-vals-frame ( var frame -- bool ) - 2dup frame-vars vars obj! - frame-vals vals obj! +: get-vals-frame ( var frame -- vals | nil ) + 2dup frame-vars + 2swap frame-vals ( var vars vals ) begin - vars obj@ nil objeq? false = + nil? false = while - 2dup vars obj@ car objeq? if - 2drop true + + -2rot ( vals var vars ) + 2over 2over car objeq? if + 2drop 2drop exit then - vars obj@ cdr vars obj! - vals obj@ cdr vals obj! + cdr 2rot cdr repeat - 2drop false + 2drop 2drop 2drop + nil ; -: get-vars-vals ( var env -- vars? vals? bool ) +: get-vals ( var env -- vals | nil ) begin nil? false = while 2over 2over first-frame - get-vars-vals-frame if - 2drop 2drop - vars obj@ vals obj@ true + get-vals-frame nil? false = if + 2swap 2drop 2swap 2drop exit then + 2drop + enclosing-env repeat - 2drop 2drop - false + 2swap 2drop ; -hide vars -hide vals - -objvar var - +objvar var \ Used only for error messages : lookup-var ( var env -- val ) 2over var obj! - get-vars-vals if - 2swap 2drop car - else - except-message: ." tried to read unbound variable '" var obj@ print ." '." recoverable-exception throw + + get-vals nil? if + except-message: ." tried to read unbound variable '" var obj@ print ." '." + recoverable-exception throw then + + car ; : set-var ( var val env -- ) - >R >R 2swap R> R> ( val var env ) - 2over var obj! - get-vars-vals if - 2swap 2drop ( val vals ) - set-car! + 2rot 2dup var obj! ( val env var ) + 2swap ( val var env ) + get-vals nil? if + except-message: ." tried to set unbound variable '" var obj@ print ." '." + recoverable-exception throw else - except-message: ." tried to set unbound variable '" var obj@ print ." '." recoverable-exception throw + ( val vals ) + set-car! then ; - hide var -objvar env - : define-var ( var val env -- ) - env obj! + first-frame ( var val frame ) + 2rot 2swap 2over 2over ( val var frame var frame ) - 2over env obj@ ( var val var env ) - get-vars-vals if - 2swap 2drop ( var val vals ) - set-car! + get-vals-frame nil? if 2drop - else - env obj@ - first-frame ( var val frame ) + -2rot 2swap 2rot add-binding + else + ( val var frame vals ) + 2swap 2drop 2swap 2drop + set-car! then ; -hide env - : make-procedure ( params body env -- proc ) nil cons cons cons @@ -521,6 +520,127 @@ global-env obj! \ }}} +\ ---- Continuations ---- {{{ + +: cons-return-stack ( -- listobj ) + rsp@ 1- rsp0 = if + nil exit + then + + nil rsp@ 1- rsp0 do + i 1+ @ fixnum-type 2swap cons + loop + + rsp@ 1- rsp0 - fixnum-type 2swap cons +; + +: cons-param-stack ( -- listobj ) + nil + + depth 2- object-stack-base @ = if + exit + then + + depth 2- object-stack-base @ do + PSP0 i + 1 + @ + PSP0 i + 2 + @ + + 2swap cons + 2 +loop + + depth 2- 2/ fixnum-type 2swap cons +; + +: make-continuation ( -- continuation true-obj ) + \ true-obj allows calling code to detect whether + \ it is being called immediately following make-continuation + \ or by a restore-continuation. + + cons-param-stack + cons-return-stack + cons drop continuation-type + + true boolean-type +; + +: continuation->pstack-list + drop pair-type car ; + +: continuation->rstack-list + drop pair-type cdr ; + +: stack-list-len ( stack-list -- n ) + car drop +; + +: restore-param-stack ( continuation -- obj_stack ) + continuation->pstack-list + 2dup >R >R + + ( Allocate stack space first using psp!, + then copy objects from list. ) + + car drop 2* + object-stack-base @ psp0 + + psp! + + R> R> 2dup cdr + 2swap + stack-list-len 1- 0 swap do + + 2dup car + PSP0 object-stack-base @ + i 2* + 2 + ! + PSP0 object-stack-base @ + i 2* + 1 + ! + cdr + + -1 +loop + + 2drop +; + +: restore-return-stack ( continuation -- ) + + continuation->rstack-list + + 2dup cdr 2swap stack-list-len ( list n ) + + dup RSP0 + RSP! \ expand return stack to accommodate entries + + ( list n ) + + 1- \ initial offset n-1 + 0 \ final offset 0 + swap + do + 2dup cdr 2swap car drop + RSP0 i 1+ + ! + -1 +loop + + 2drop +; + +: restore-continuation-with-arg ( continuation obj -- ) + + >R >R \ Store obj on return stack + + 2dup >R >R \ Store copy of continuation on return stack + + restore-param-stack + + R> R> \ Pop continuation from return stack + + R> R> \ Pop obj from return stack + + 2swap + + false boolean-type \ Add flag signifying continuation restore + + 2swap + + restore-return-stack +; + +\ }}} + \ ---- Primitives ---- {{{ : make-primitive ( cfa -- ) @@ -1273,6 +1393,11 @@ parse-idx-stack parse-idx-sp ! exit then + nextchar [char] ) = if + inc-parse-idx + except-message: ." unmatched closing parenthesis." recoverable-exception throw + then + \ Anything else is parsed as a symbol readsymbol charlist>symbol @@ -1286,7 +1411,7 @@ parse-idx-stack parse-idx-sp ! \ }}} -\ ---- Eval ---- {{{ +\ ---- Syntax ---- {{{ : self-evaluating? ( obj -- obj bool ) boolean-type istype? if true exit then @@ -1315,95 +1440,6 @@ parse-idx-stack parse-idx-sp ! : quote-body ( quote-obj -- quote-body-obj ) cdr car ; -: quasiquote? ( obj -- obj bool ) - quasiquote-symbol tagged-list? ; - -: unquote? ( obj -- obj bool ) - unquote-symbol tagged-list? ; - -: unquote-splicing? ( obj -- obj bool ) - unquote-splicing-symbol tagged-list? ; - -: eval-unquote ( env obj -- res ) - cdr ( env args ) - - nil? if - except-message: ." no arguments to unquote." recoverable-exception throw - then - - 2dup cdr - nil? false = if - except-message: ." too many arguments to unquote." recoverable-exception throw - then - - 2drop car 2swap eval -; - -( Create a new list from elements of l1 consed on to l2 ) -: join-lists ( l2 l1 -- l3 ) - nil? if 2drop exit then - - 2dup car - -2rot cdr - recurse cons -; - -defer eval-quasiquote-item -: eval-quasiquote-pair ( env obj -- res ) - 2over 2over ( env obj env obj ) - - cdr eval-quasiquote-item - - -2rot car ( cdritem env objcar ) - - unquote-splicing? if - eval-unquote ( cdritems caritem ) - - 2swap nil? if - 2drop - else - 2swap join-lists - then - else - eval-quasiquote-item ( cdritems caritem ) - 2swap cons - then - -; - -:noname ( env obj ) - nil? if - 2swap 2drop exit - then - - unquote? if - eval-unquote exit - then - - pair-type istype? if - eval-quasiquote-pair exit - then - - 2swap 2drop -; is eval-quasiquote-item - -: eval-quasiquote ( obj env -- res ) - 2swap cdr ( env args ) - - nil? if - except-message: ." no arguments to quasiquote." recoverable-exception throw - then - - 2dup cdr ( env args args-cdr ) - nil? false = if - except-message: ." too many arguments to quasiquote." recoverable-exception throw - then - - 2drop car ( env arg ) - - eval-quasiquote-item -; - : variable? ( obj -- obj bool ) symbol-type istype? ; @@ -1416,20 +1452,6 @@ defer eval-quasiquote-item : definition-val ( obj -- val ) cdr cdr car ; -: eval-definition ( obj env -- res ) - 2swap - 2over 2over - definition-val 2swap - eval - - 2swap definition-var 2swap - - 2rot - define-var - - ok-symbol -; - : assignment? ( obj -- obj bool ) set!-symbol tagged-list? ; @@ -1439,20 +1461,6 @@ defer eval-quasiquote-item : assignment-val ( obj -- val ) cdr cdr car ; -: eval-assignment ( obj env -- res ) - 2swap - 2over 2over ( env obj env obj ) - assignment-val 2swap ( env obj valexp env ) - eval ( env obj val ) - - 2swap assignment-var 2swap ( env var val ) - - 2rot ( var val env ) - set-var - - ok-symbol -; - : macro-definition? ( obj -- obj bool ) define-macro-symbol tagged-list? ; @@ -1465,22 +1473,6 @@ defer eval-quasiquote-item : macro-definition-body ( exp -- body ) cdr cdr ; -objvar env -: eval-define-macro ( obj env -- res ) - env obj! - - 2dup macro-definition-name 2swap ( name obj ) - 2dup macro-definition-params 2swap ( name params obj ) - macro-definition-body ( name params body ) - - env obj@ ( name params body env ) - - make-macro - - ok-symbol -; -hide env - : if? ( obj -- obj bool ) if-symbol tagged-list? ; @@ -1518,32 +1510,6 @@ hide env : lambda-body ( obj -- body ) cdr cdr ; -: eval-sequence ( explist env -- finalexp env ) - ( Evaluates all bar the final expressions in - an an expression list. The final expression - is returned to allow for tail optimization. ) - - 2swap ( env explist ) - - \ Abort on empty list - nil? if - 2drop none - 2swap exit - then - - begin - 2dup cdr ( env explist nextexplist ) - nil? false = - while - -2rot car 2over ( nextexplist env exp env ) - eval - 2drop \ discard result - 2swap ( env nextexplist ) - repeat - - 2drop car 2swap ( finalexp env ) -; - : application? ( obj -- obj bool ) pair-type istype? ; @@ -1562,18 +1528,6 @@ hide env : rest-operands ( operands -- other-operands ) cdr ; -: list-of-vals ( args env -- vals ) - 2swap - - 2dup nooperands? if - 2swap 2drop - else - 2over 2over first-operand 2swap eval - -2rot rest-operands 2swap recurse - cons - then -; - : procedure-params ( proc -- params ) drop pair-type car ; @@ -1618,121 +1572,9 @@ hide env 2swap ; -: apply ( proc argvals -- result ) - 2swap dup case - primitive-proc-type of - drop execute - endof - - compound-proc-type of - 2dup procedure-body ( argvals proc body ) - -2rot 2dup procedure-params ( body argvals proc argnames ) - -2rot procedure-env ( body argnames argvals procenv ) - - -2rot 2swap - flatten-proc-args - 2swap 2rot - - extend-env ( body env ) - - eval-sequence - - R> drop ['] eval goto-deferred \ Tail call optimization - endof - - except-message: ." object '" drop print ." ' not applicable." recoverable-exception throw - endcase -; - -:noname ( obj env -- result ) - 2swap - - \ --- DEBUG --- - ( - fg yellow ." Evaluating: " bold 2dup print reset-term - space fg green ." PS: " bold depth . reset-term - space fg blue ." RS: " bold RSP@ RSP0 - . reset-term cr - ) - - self-evaluating? if - 2swap 2drop - exit - then - - quote? if - quote-body - 2swap 2drop - exit - then - - quasiquote? if - 2swap eval-quasiquote - exit - then - - variable? if - 2swap lookup-var - exit - then - - definition? if - 2swap eval-definition - exit - then - - assignment? if - 2swap eval-assignment - exit - then - - macro-definition? if - 2swap eval-define-macro - exit - then - - if? if - 2over 2over - if-predicate - 2swap eval - - true? if - if-consequent - else - if-alternative - then - - 2swap - ['] eval goto-deferred - then - - lambda? if - 2dup lambda-parameters - 2swap lambda-body - 2rot make-procedure - exit - then - - application? if - - 2over 2over ( env exp env exp ) - operator ( env exp env opname ) - - 2swap eval ( env exp proc ) - - -2rot ( proc env exp ) - operands 2swap ( proc operands env ) - list-of-vals ( proc argvals ) - - apply - exit - then - - except-message: ." tried to evaluate object with unknown type." recoverable-exception throw -; is eval - \ }}} -\ ---- Analyze ---- +\ ---- Analyze ---- {{{ : evaluate-eproc ( eproc env --- res ) @@ -1752,8 +1594,6 @@ hide env \ Final element of eproc list is primitive procedure drop \ dump type signifier - .s cr \ DEBUG - goto \ jump straight to primitive procedure (executor) ; @@ -1813,28 +1653,6 @@ hide env nil cons cons cons ; -: if-executor ( cproc aproc pproc env -- res ) - 2swap 2over ( cproc aproc env pproc env -- res ) - evaluate-eproc - - true? if - 2swap 2drop - else - 2rot 2drop - then - - evaluate-eproc -; - -: analyze-if ( exp -- eproc ) - 2dup if-predicate analyze - 2swap 2dup if-consequent analyze - 2swap if-alternative analyze - - ['] if-executor primitive-proc-type - nil cons cons cons cons -; - : sequence-executor ( eproc-list env -- res ) 2swap @@ -1842,7 +1660,6 @@ hide env 2dup cdr ( env elist elist-rest) nil? invert while - -2rot car 2over ( elist-rest env elist-head env ) evaluate-eproc ( elist-rest env head-res ) 2drop 2swap ( env elist-rest ) @@ -1868,6 +1685,42 @@ hide env nil cons cons ; + +: macro-definition-executor ( name params bproc env -- ok ) + make-macro ok-symbol +; + +: analyze-macro-definition ( exp -- eproc ) + 2dup macro-definition-name + 2swap 2dup macro-definition-params + 2swap macro-definition-body analyze-sequence + + ['] macro-definition-executor primitive-proc-type + nil cons cons cons cons +; + +: if-executor ( cproc aproc pproc env -- res ) + 2swap 2over ( cproc aproc env pproc env -- res ) + evaluate-eproc + + true? if + 2swap 2drop + else + 2rot 2drop + then + + ['] evaluate-eproc goto +; + +: analyze-if ( exp -- eproc ) + 2dup if-consequent analyze + 2swap 2dup if-alternative analyze + 2swap if-predicate analyze + + ['] if-executor primitive-proc-type + nil cons cons cons cons +; + : lambda-executor ( params bproc env -- res ) make-procedure ( Although this is packaged up as a regular compound procedure, @@ -1908,22 +1761,14 @@ hide env then ; -: application-executor ( operator-proc arg-procs env -- res ) - 2rot 2over ( aprocs env fproc env ) - evaluate-eproc ( aprocs env proc ) - - -2rot 2swap ( proc env aprocs ) - evaluate-operand-eprocs ( proc vals ) - - 2swap ( vals proc ) - +: apply ( vals proc ) dup case primitive-proc-type of drop execute endof compound-proc-type of - 2dup procedure-body ( argvals proc body ) + 2dup procedure-body ( argvals proc bproc ) -2rot 2dup procedure-params ( bproc argvals proc argnames ) -2rot procedure-env ( bproc argnames argvals procenv ) @@ -1936,10 +1781,41 @@ hide env ['] evaluate-eproc goto endof + continuation-type of + 2swap + nil? if + except-message: ." Continuations expect exactly 1 argument." + recoverable-exception throw + then + + 2dup cdr + + nil? invert if + except-message: ." Continuations expect exactly 1 argument." + recoverable-exception throw + then + + 2drop car + + restore-continuation-with-arg + endof + except-message: ." object '" drop print ." ' not applicable." recoverable-exception throw endcase ; +: application-executor ( operator-proc arg-procs env -- res ) + 2rot 2over ( aprocs env fproc env ) + evaluate-eproc ( aprocs env proc ) + + -2rot 2swap ( proc env aprocs ) + evaluate-operand-eprocs ( proc vals ) + + 2swap ( vals proc ) + + ['] apply goto +; + : analyze-application ( exp -- eproc ) 2dup operator analyze 2swap operands operand-eproc-list @@ -1950,74 +1826,54 @@ hide env :noname ( exp --- eproc ) - self-evaluating? if - analyze-self-evaluating - exit - then + self-evaluating? if analyze-self-evaluating exit then - quote? if - analyze-quoted - exit - then + quote? if analyze-quoted exit then - variable? if - analyze-variable - exit - then + variable? if analyze-variable exit then - definition? if - analyze-definition - exit - then + definition? if analyze-definition exit then - assignment? if - analyze-assignment - exit - then + assignment? if analyze-assignment exit then - if? if - analyze-if - exit - then + macro-definition? if analyze-macro-definition exit then - lambda? if - analyze-lambda - exit - then + if? if analyze-if exit then - application? if - analyze-application - exit - then + lambda? if analyze-lambda exit then + + application? if analyze-application exit then - except-message: ." tried to analyze unknown expression type." recoverable-exception throw ; is analyze +\ }}} \ ---- Macro Expansion ---- {{{ ( Simply evaluates the given procedure with expbody as its argument. ) : macro-eval ( proc expbody -- result ) 2swap - 2dup procedure-body ( expbody proc procbody ) - -2rot 2dup procedure-params ( procbody expbody proc argnames ) - -2rot procedure-env ( procbody argnames expbody procenv ) + 2dup procedure-body ( expbody proc bproc ) + -2rot 2dup procedure-params ( bproc expbody proc argnames ) + -2rot procedure-env ( bproc argnames expbody procenv ) -2rot 2swap flatten-proc-args 2swap 2rot - extend-env eval-sequence eval + extend-env ( bproc env ) + + ['] evaluate-eproc goto ; : expand-macro ( exp -- result ) pair-type istype? invert if exit then + 2dup car symbol-type istype? invert if 2drop exit then - - lookup-macro nil? if - 2drop exit then + + lookup-macro nil? if 2drop exit then 2over cdr macro-eval @@ -2030,33 +1886,6 @@ hide env R> drop ['] expand goto-deferred ; -: expand-quasiquote-item ( exp -- result ) - nil? if exit then - - unquote? if - unquote-symbol 2swap cdr car expand nil cons cons - exit - then - - unquote-splicing? if - unquote-splicing-symbol 2swap cdr car expand nil cons cons - exit - then - - pair-type istype? if - 2dup car recurse - 2swap cdr recurse - cons - then -; - -: expand-quasiquote ( exp -- result ) - quasiquote-symbol 2swap cdr - - expand-quasiquote-item - - cons ; - : expand-definition ( exp -- result ) define-symbol 2swap @@ -2126,8 +1955,6 @@ hide env quote? if exit then - quasiquote? if expand-quasiquote exit then - definition? if expand-definition exit then assignment? if expand-assignment exit then @@ -2144,6 +1971,10 @@ hide env \ }}} +:noname ( exp env -- res ) + 2swap expand analyze 2swap evaluate-eproc +; is eval + \ ---- Print ---- {{{ : printfixnum ( fixnum -- ) drop 0 .R ; @@ -2217,6 +2048,9 @@ hide env : printcomp ( primobj -- ) 2drop ." " ; +: printcont ( primobj --) + 2drop ." " ; + : printnone ( noneobj -- ) 2drop ." Unspecified return value" ; @@ -2235,6 +2069,7 @@ hide env pair-type istype? if ." (" printpair ." )" exit then primitive-proc-type istype? if printprim exit then compound-proc-type istype? if printcomp exit then + continuation-type istype? if printcont exit then none-type istype? if printnone exit then port-type istype? if printport exit then @@ -2245,20 +2080,20 @@ hide env \ ---- Garbage Collection ---- {{{ -variable gc-enabled -false gc-enabled ! +( Notes on garbage collection: + This is a mark-sweep garbage collector, invoked by cons. + The roots of the object tree used by the marking routine + include all objects in the parameter stack, and several + other fixed roots such as global-env, symbol-table, macro-table, + and the console-i/o-port. -variable gc-stack-depth + NO OTHER OBJECTS WILL BE MARKED! -: enable-gc - depth gc-stack-depth ! - true gc-enabled ! ; + This places implicit restrictions on when cons can be invoked. + Invoking cons when live objects are stored on the return stack + or in other variables than the above will result in possible + memory corruption if the cons triggers the GC. ) -: disable-gc - false gc-enabled ! ; - -: gc-enabled? - gc-enabled @ ; : pairlike? ( obj -- obj bool ) pair-type istype? if true exit then @@ -2266,6 +2101,7 @@ variable gc-stack-depth symbol-type istype? if true exit then compound-proc-type istype? if true exit then port-type istype? if true exit then + continuation-type istype? if true exit then false ; @@ -2335,7 +2171,7 @@ variable gc-stack-depth console-i/o-port obj@ gc-mark-obj global-env obj@ gc-mark-obj - depth gc-stack-depth @ do + depth object-stack-base @ do PSP0 i + 1 + @ PSP0 i + 2 + @ @@ -2359,8 +2195,14 @@ variable gc-stack-depth ok-symbol ( port res ) begin + \ DEBUG + \ bold fg blue ." READ from " 2over drop . ." ==> " reset-term + 2over read-port ( port res obj ) + \ DEBUG + \ 2dup print cr + 2dup EOF character-type objeq? if 2drop 2swap close-port exit @@ -2368,8 +2210,6 @@ variable gc-stack-depth 2swap 2drop ( port obj ) - expand - global-env obj@ eval ( port res ) again ; @@ -2380,7 +2220,8 @@ variable gc-stack-depth include scheme-primitives.4th - \ s" scheme-library.scm" load 2drop + init-object-stack-base + s" scheme-library.scm" load 2drop \ }}} @@ -2398,8 +2239,6 @@ variable gc-stack-depth true exit then - expand - global-env obj@ eval fg cyan ." ; " print reset-term @@ -2410,10 +2249,10 @@ variable gc-stack-depth : repl empty-parse-str - enable-gc + init-object-stack-base \ Display welcome message - \ welcome-symbol nil cons global-env obj@ eval 2drop + welcome-symbol nil cons global-env obj@ eval 2drop begin ['] repl-body catch