REBOL [ File: %multi-methods.r Date: 11-Apr-2005 Title: "Multi-methods implementation" Version: 1.4.0 Author: "Jaime Vargas" Rights: {Copyright © Jaime Vargas, Why Wire, Inc. 2005} Purpose: {Implements polyformism using multi-methods technique and typed objects} library: [ level: 'intermediate platform: 'all type: 'tool domain: [dialects extension math scientific] tested-under: none support: none license: 'BSD see-also: none ] ] time-it: func [code [block!] /local start time][ start: now/time/precise do code time: now/time/precise - start print [mold code "->" time] ] unfold-native: func [ name [word!] dispatch-table [series!] /local f spec arg-types b refinement-rule parameter-rule locals-rule spec-rule i-vars blocks code permutations ][ f: get name spec: third :f arg-types: copy [] refinement-rule: [refinement! opt word! opt block! opt string! end skip] ;force fail parameter-rule: [word! set b block! (insert/only tail arg-types b) opt string!] locals-rule: [/local some [word!]] spec-rule: [opt string! some [refinement-rule | parameter-rule] opt locals-rule] unless parse spec spec-rule [throw make error join "Can't overload " :name] i-vars: copy [] ;vars for the iterators blocks: copy [] ;vars for the blocks repeat i length? arg-types [ insert tail i-vars to-word join 'i i insert tail blocks to-word join 'b i replace/all arg-types/:i number! [integer! decimal!] ;make types explicit ] code: copy "[" repeat i length? arg-types [ insert tail code form compose [foreach (i-vars/:i) (blocks/:i) "["] ] insert tail code mold/only compose/only [insert/only tail permutations reduce (i-vars)] insert/dup tail code "]" 1 + length? arg-types code: load form code permutations: copy [] use blocks [ set blocks arg-types do bind code 'arg-types ] foreach spec permutations [ insert tail dispatch-table reduce [mold spec :f] ] ] define-method: func [ [catch] 'name [word!] spec [block!] code [block!] /trace /local arg-spec fp-spec locals t v w name-rule type-rule continue? param-spec-rule monad-types monad-rule monad-rule-spec local-rule spec-rule register-name methods-name ][ ;; first validate the spec arg-spec: copy [] fp-spec: copy [] locals: copy [] continue?: [none] ;used to stop parsing ;; spec as a parameter specification list name-rule: [set w set-word!] type-rule: [set t word! (unless datatype? attempt [get t] [continue?: [end skip]])] param-spec-rule: [some [name-rule type-rule continue? ( insert tail arg-spec reduce [to-word :w reduce [:t]] insert tail fp-spec :t )]] ;; spec as a monadic specification list monad-types: [number! | money! | pair! | tuple! | any-string! | date! | time!] monad-rule: [set v monad-types] monad-spec-rule: [some [name-rule monad-rule (insert tail fp-spec reduce [:v])]] local-rule: [/local some [ set w word! ( if result: find arg-spec :w [continue?: [end skip]] insert tail locals :w) continue?] ] spec-rule: [[param-spec-rule | monad-spec-rule] opt local-rule ] unless parse spec spec-rule [throw make error! "invalid spec"] register-name: to-word join :name '-register methods-name: to-word join :name '-methods? unless all [value? name value? methods-name] [ if find [op!] type?/word attempt [get name] [throw make error! join "Can't overload " :name] context [ dispatch-table: make block! [] if find [action!] type?/word attempt [get name][ unfold-native :name dispatch-table ] spec-fingerprint: func [spec [block!] /local types][ extract/index spec 2 2 ] values-fingerprint: func [values [block!] /local types][ types: copy [] foreach v values [insert tail types type?/word v] types ] retrieve-func: func [values [block!] /local f fp][ if f: select/only dispatch-table mold values [return compose [(:f) (true)]] ;monadic fingerprint either f: select/only dispatch-table fp: mold values-fingerprint values [compose [(:f) (false)]][ throw make error! reform ["Don't have a method to handle:" fp] ] ] set :name func [[catch] values [block!] /local f monadic] compose [ values: reduce values set [f monadic] retrieve-func values (either trace [ [ probe do probe compose either monadic [ [(:f)] ][ [(:f) (values)] ] ] ][ [ do compose either monadic [ [(:f)] ][ [(:f) (values)] ] ] ]) ] set :register-name func [fp-spec spec locals code /local fingerprint pos][ either found? pos: find/only dispatch-table fp-spec [ poke dispatch-table 1 + index? pos function spec locals code ][ insert tail dispatch-table reduce [mold fp-spec function spec locals code] ] ] set :methods-name does [ foreach [fp f] dispatch-table [ print [:fp "->" mold either 'action! = type?/word :f [:f][second :f]] ] ] ] ] do reduce [register-name fp-spec arg-spec locals code] none ] comment [ ;;Usage examples ;define-method creates a "fingerprint" for each parameter-spec ;and evals corresponding code according to "fingerprint" define-method f [x: integer!] [x + 1] define-method f [s: block!] [attempt [pick s 2]] define-method f [x: decimal!] [sine x] >> f[1] == 2 >> f[[one two three]] == two >> b: [one two three] >> f[b] == two >> f[90.0] == 1.0 ;instrospection one can always see the methods of a function >> f-methods? ;[integer!] -> [x + 1] ;[block!] -> [attempt [pick s 2]] ;[decimal!] -> [sine x] ;singleton parameter specs are posible. ;This allows for "rule" based programming define-method fact [n: 0] [1] define-method fact [n: integer!][n * fact[n - 1]] >> fact-methods? ;[0] -> [1] ;[integer!] -> [n * fact [n - 1]] ;now that we have singletons we can use memoization techniques define-method fact-memoize [n: 0] [1] define-method fact-memoize [n: integer! /local r ][ r: n * fact[n - 1] define-method fact-memoize compose [n: (:n)] reduce [r] r ] >> time-it [fact[12]] == 0:00:00.000434 ;no memoization >> time-it [fact-memoize[12]] == 0:00:00.000583 ;first invoication >> time-it [fact-memoize[12]] == 0:00:00.000087 ;cache lookup ;dispatch for undefined type signals error >> fact[1.0] ** User Error: Don't have a method to handle: [decimal!] ** Near: fact [1.0] ;moization is more dramatic when calculating the fibonacci sequence define-method fib [n: 1] [1] define-method fib [n: 2] [1] define-method fib [n: integer!][ add fib[n - 2] fib[n - 1] ] define-method fib-memoize [n: 1] [1] define-method fib-memoize [n: 2] [1] define-method fib-memoize [n: integer! /local r][ r: add fib-memoize[n - 1] fib-memoize[n - 2] define-method fib-memoize compose [n: (:n)] reduce [r] r ] ;without memoization >> time-it [fib [20]] == 0:00:00.32601 >> time-it [fib [19]] == 0:00:00.207066 ;dramatic gains due to memoization >> time-it [fib-memoize[20]] == 0:00:00.002187 ;first invoication >> time-it [fib-memoize[20]] == 0:00:00.000096 ;cache lookup >> time-it [fib-memoize[19]] == 0:00:00.0001 ;cache lookup ;it is possible to overload some natives! define-method add [x: issue! y: issue!][join x y] add[1 1] == 2 add[1.0.0 1] == 2.1.1 add[#abc #def] == #abcdef ] define-object: func [ spec [block!] /local arg-spec ctx-spec object-name constructor-name predicate-name attributes spec-rule type-spec continue? w ][ arg-names: copy [] continue?: [none] ;used to stop parsing name-rule: [set w word! (insert tail arg-names w)] type-rule: [set w word! (unless datatype? attempt [get w] [continue?: [end skip]])] spec-rule: [name-rule some [name-rule opt [into [some [type-rule continue?]]]]] either any [ not parse spec spec-rule arg-names <> unique arg-names ][ make error! "invalid spec" ] object-name: to-string first arg-names constructor-name: to-word join 'make- object-name predicate-name: to-word join object-name '? attributes: next arg-names arg-spec: copy [] foreach itm attributes [ insert tail arg-spec reduce [ to-word join itm '-value either block? w: select spec itm [w][[any-type!]] ] ] ctx-spec: copy [] arg-names: extract arg-spec 2 1 repeat i length? attributes [ insert tail ctx-spec reduce [to-set-word attributes/:i to-get-word arg-names/:i] ] ;create constructor function set constructor-name make function! compose [(reform ["Makes a new" uppercase object-name "object with attributes" mold attributes]) (arg-spec)] compose/only [make object! (ctx-spec)] ;body ;create predicate function set predicate-name make function! compose [(reform ["Determines if value is a" uppercase object-name "object"]) value [object!] /local types] compose/deep/only [ if (attributes) <> next first value [return false] foreach itm (attributes) [ unless any [ [any-type!] = types: select (arg-spec) to-word join itm '-value find types type?/word value/:itm ][return false] ] true ] ] comment [ ;; Usage examples define-object [point x [integer!] y [integer!]] point? make-point 1 1 == true point? context [x: 1 y: 1] == true point? context [x: "abc" y: "cde"] == false make-point "abc" "cde" == error! ]