Shen for CLR passing standard test suite

[Robert Koeninger]

So I'm finally following up to some talk of mine last year about getting Shen running on .Net/Mono.

https://github.com/rkoeninger/ShenSharp

I took some time the past couple of weeks and finally fixed the remaining issues with the interpreter and it now passes all tests in the standard test suite for Shen 19.2.

Test output:

https://gist.github.com/rkoeninger/2f29ca2f6d5ab88c8f4dccacc4def3fc

(timestamps are off, I fixed that)

It was developed in F# using Visual Studio and has been mainly tested in .Net on Windows, but is also shown to work in Mono on Linux (considering the build on Travis-CI is functional).

I have plans for improving its slow performance, including pre-rendering the initial KL environment to F#, compilation of the KL code, on-demand compilation, pre-compilation... maybe a Visual Studio plugin for Shen projects that compiles Shen into a CLR assembly... the sky's the limit.

When the implementation is built into a single Shen.dll/Shen.exe, I'll try to get a Nuget package published so it can easily be referenced by .net projects.

[deech]

This is awesome! Thanks for making it.

[Mark Tarver]

A bit snowed under here.  But I just got the time and had a look at this.

First, congratulations on doing this Robert.

Second kudos for the awesome patience.  Do I read that right?

run time: 813421 secs

The standard tests actually took 225 hours to run or nearly 9 1/2 days?  Wow.

Mark :)

[Bruno Deferrari]

On Sat, Jan 21, 2017 at 7:59 PM, Robert Koeninger <robertk...@gmail.com> wrote:

So I'm finally following up to some talk of mine last year about getting Shen running on .Net/Mono.

https://github.com/rkoeninger/ShenSharp

I took some time the past couple of weeks and finally fixed the remaining issues with the interpreter and it now passes all tests in the standard test suite for Shen 19.2.

Test output:

https://gist.github.com/rkoeninger/2f29ca2f6d5ab88c8f4dccacc4def3fc

(timestamps are off, I fixed that)

It was developed in F# using Visual Studio and has been mainly tested in .Net on Windows, but is also shown to work in Mono on Linux (considering the build on Travis-CI is functional).

I have plans for improving its slow performance, including pre-rendering the initial KL environment to F#, compilation of the KL code, on-demand compilation, pre-compilation... maybe a Visual Studio plugin for Shen projects that compiles Shen into a CLR assembly... the sky's the limit.

Thats pretty cool. I'm going through the source code, it is very readable (and I don't even do F# or .NET myself).

IIRC F# has a "code quotations" feature, that lets you work with F# expressions (generate, match, modify, etc) and then compile them, would that be a viable approach? It is probably not the one that would generate the most optimal CLR assembly, but sounds much easier to implement.

Btw you can take advantage of Shen's system functions not being overrideable by user code and skip the lookup for those at evaluation time (so in such cases where the function is a primitive, instead of emitting a 'Sym s' you lookup it that moment and emit a 'Func f' instead). From looking at the implementation it seems to me that right now a lot of time is spent on doing function lookups, so I would guess this would have a big impact.

 

When the implementation is built into a single Shen.dll/Shen.exe, I'll try to get a Nuget package published so it can easily be referenced by .net projects.

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Robert Koeninger]

My (get-time) was off by 100x I think, but, yeah, it took over an hour.

I was pushing off optimization work until I had a working baseline.

[Robert Koeninger]

I was just about to ask about core functions being redefineable.

Yeah, I could emit a (Func f) or if the symbol is in operator position, or I could even just call it directly, right?

(define @s X Y -> (cn X Y))

becomes

let ``@s`` globals = function
    | [argX; argY] -> Builtins.klConcat globals [argX; argY]
    | args -> argsErr "@s" args
globals.Functions.["@s"] <- Native("@s", 2, ``@s``)

instead of

| [argX; argY] -> Evaluator.apply globals (globals.Functions.["cn"]) [argX; argY]

On Sunday, January 22, 2017 at 11:43:40 AM UTC-5, Bruno Deferrari wrote:

Btw you can take advantage of Shen's system functions not being overrideable by user code and skip the lookup for those at evaluation time (so in such cases where the function is a primitive, instead of emitting a 'Sym s' you lookup it that moment and emit a 'Func f' instead). From looking at the implementation it seems to me that right now a lot of time is spent on doing function lookups, so I would guess this would have a big impact.

--

BD

[Bruno Deferrari]

To get a list of system functions (which are not redefinable by users) you can do this:

(get shen shen.external-symbols)

or see https://github.com/Shen-Language/shen-sources/blob/eb64276a74cca00cbe991fa1e6d76ea2caf8ba63/sources/declarations.shen#L107-L124

And here is the code that ensures that they are not redefined: https://github.com/Shen-Language/shen-sources/blob/eb64276a74cca00cbe991fa1e6d76ea2caf8ba63/sources/core.shen#L44-L47

Users can declare other functions as being system functions by using (systemf some-name), thats something else you can take advantage of is you happen to track calls to systemf in your evaluator, but will not have nearly as much effect as doing so just for the default system functions.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Robert Koeninger]

Got compilation implemented. ShenSharp now generates code with direct references between system functions, e.g.

(defun f (X) ...)

(defun g () ... (f X) ...)

becomes

let kl_f globals [kl_X] = ...

let kl_g globals [] = ... (kl_f globals [kl_X]) ...

Anyway, it results in a 12x performance increase. Test result output

Tests now finish in about 11 minutes.

[Bruno Deferrari]

On Tue, Feb 14, 2017 at 11:22 PM, Robert Koeninger <robertk...@gmail.com> wrote:

Got compilation implemented. ShenSharp now generates code with direct references between system functions, e.g.

(defun f (X) ...)

(defun g () ... (f X) ...)

becomes

let kl_f globals [kl_X] = ...

let kl_g globals [] = ... (kl_f globals [kl_X]) ...

Anyway, it results in a 12x performance increase. Test result output

Tests now finish in about 11 minutes.

Thats great!

Do .NET dictionaries let you do lookup with pre-hashed keys? If you can do that, my guess is that by pre-hashing the function names at compile time, it should give you another good improvement in performance, because then function applications would no longer have to pay the cost of hashing.

 

On Sunday, January 22, 2017 at 1:01:43 AM UTC-5, Robert Koeninger wrote:

So I'm finally following up to some talk of mine last year about getting Shen running on .Net/Mono.

https://github.com/rkoeninger/ShenSharp

I took some time the past couple of weeks and finally fixed the remaining issues with the interpreter and it now passes all tests in the standard test suite for Shen 19.2.

Test output:

https://gist.github.com/rkoeninger/2f29ca2f6d5ab88c8f4dccacc4def3fc

(timestamps are off, I fixed that)

It was developed in F# using Visual Studio and has been mainly tested in .Net on Windows, but is also shown to work in Mono on Linux (considering the build on Travis-CI is functional).

I have plans for improving its slow performance, including pre-rendering the initial KL environment to F#, compilation of the KL code, on-demand compilation, pre-compilation... maybe a Visual Studio plugin for Shen projects that compiles Shen into a CLR assembly... the sky's the limit.

When the implementation is built into a single Shen.dll/Shen.exe, I'll try to get a Nuget package published so it can easily be referenced by .net projects.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Mark Tarver]

Well done.    Do you want me to put it on the download page?  If so, can you pass some official links for this?

While I'm at it, anybody else got any downloads for this page. - I'll put them up.

Mark

[Bruno Deferrari]

On Wed, Feb 15, 2017 at 9:40 AM, Bruno Deferrari <uti...@gmail.com> wrote:

On Tue, Feb 14, 2017 at 11:22 PM, Robert Koeninger <robertk...@gmail.com> wrote:

Got compilation implemented. ShenSharp now generates code with direct references between system functions, e.g.

(defun f (X) ...)

(defun g () ... (f X) ...)

becomes

let kl_f globals [kl_X] = ...

let kl_g globals [] = ... (kl_f globals [kl_X]) ...

Anyway, it results in a 12x performance increase. Test result output

Tests now finish in about 11 minutes.

Thats great!

Do .NET dictionaries let you do lookup with pre-hashed keys? If you can do that, my guess is that by pre-hashing the function names at compile time, it should give you another good improvement in performance, because then function applications would no longer have to pay the cost of hashing.

 

Ok, .NET probably doesn't have this (neither does any language/platform I know), but there is a better solution.

If you define your own datatype for symbols, so that it contains an interned string and a pre-calculated hash value for that string stored in another field (something like { hash: int; name: string; } ), with a custom GetHashCode() method that just returns the value in that field then you will still get the benefits.

An extra step required is that when you construct instances of such symbols using a string "something", you have to do a lookup to see if it already exists, and if so, return the existing instance matching "something", if it doesn't then you create a new instance and store it.

Does this make sense?

 

On Sunday, January 22, 2017 at 1:01:43 AM UTC-5, Robert Koeninger wrote:

So I'm finally following up to some talk of mine last year about getting Shen running on .Net/Mono.

https://github.com/rkoeninger/ShenSharp

I took some time the past couple of weeks and finally fixed the remaining issues with the interpreter and it now passes all tests in the standard test suite for Shen 19.2.

Test output:

https://gist.github.com/rkoeninger/2f29ca2f6d5ab88c8f4dccacc4def3fc

(timestamps are off, I fixed that)

It was developed in F# using Visual Studio and has been mainly tested in .Net on Windows, but is also shown to work in Mono on Linux (considering the build on Travis-CI is functional).

I have plans for improving its slow performance, including pre-rendering the initial KL environment to F#, compilation of the KL code, on-demand compilation, pre-compilation... maybe a Visual Studio plugin for Shen projects that compiles Shen into a CLR assembly... the sky's the limit.

When the implementation is built into a single Shen.dll/Shen.exe, I'll try to get a Nuget package published so it can easily be referenced by .net projects.

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

--

BD

[Mark Tarver]

Good you're getting there.  Shen/SBCL takes 7.5 seconds on my 4.7GHz machine.  I ran the suite and here is a print - there may be reduplicated results because I had to scrape this off the console window.   However it may help you pinpoint where your program is slow.

false

run time: 4.133999828249216 secs

Shen, copyright (C) 2010-2015 Mark Tarver

www.shenlanguage.org, Shen Professional Edition 14

running under Common Lisp, implementation: SBCL

port 2.1 ported by Mark Tarver

commercially licensed to Mark Tarver

(0-) (* 999 999)

998001

(1-) (cd "../../Test Programs")

"../../Test Programs/"

(2-) (load "README.shen")

reset

test-harness.exec-macro

test-harness.rcons

passed

failed

test-harness.err

test-harness.report-results-macro

test-harness.create-tests

test-harness.results

run time: 0.07800006866455078 secs

loaded

(3-) (load "tests.shen")

10000000000

prolog-tests: (load "prolog.shen") = loadedf

g

mem

app

rev

enjoys

enjoys

fads

fads

prop

prop

proph

consistent

app

mem

mapit

consit

different

~

likes

tall

pretty

run time: 0.29600000381469727 secs

run time: 0.29600000381469727 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (f a NPP (freeze true))) = true

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (g a NPP (freeze true))) = false

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (g b NPP (freeze true))) = true

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let X (shen.newpv NPP) (mem 1 (cons X 2) NPP (freeze (return X NPP (freeze true)))))) = 1

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let X (shen.newpv NPP) (rev (cons 1 (cons 2 ())) X NPP (freeze (return X NPP (freeze true)))))) = [2 1]

run time: 0.0 secs

passed

prolog-tests: (load "einstein.shen") = loadedeinsteins_riddle

einstein

member

next_to

iright

run time: 0.062000274658203125 secs

run time: 0.062000274658203125 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let X (shen.newpv NPP) (einsteins_riddle X NPP (freeze (return X NPP (freeze true)))))) = german

run time: 0.07799959182739258 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let X (shen.newpv NPP) (enjoys mark X NPP (freeze (return X NPP (freeze true)))))) = chocolate

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (fads mark NPP (freeze true))) = [tea chocolate]

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (prop () (cons p (cons <=> (cons p ()))) NPP (freeze true))) = true

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let Out (shen.newpv NPP) (mapit consit (cons 1 (cons 2 (cons 3 ()))) Out NPP (freeze (return Out NPP (freeze

true)))))) = [[1 1] [1 2] [1 3]]

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (different a b NPP (freeze true))) = true

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (different a a NPP (freeze true))) = false

run time: 0.0 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (let Who (shen.newpv NPP) (likes john Who NPP (freeze (return Who NPP (freeze true)))))) = mary

run time: 0.0 secs

passed

prolog-tests: (load "parse.prl") = loadedpparse

parsing

member

run time: 0.06199979782104492 secs

run time: 0.06199979782104492 secs

passed

prolog-tests: (let NPP (shen.start-new-prolog-process) (pparse (cons "the" (cons + (cons (cons "boy" (cons + (cons "jumps" ()))) ()))) (cons (cons s (cons = (cons (c

ons np (cons + (cons vp ()))) ()))) (cons (cons np (cons = (cons (cons det (cons + (cons n ()))) ()))) (cons (cons det (cons = (cons "the" ()))) (cons (cons n (cons

= (cons "girl" ()))) (cons (cons n (cons = (cons "boy" ()))) (cons (cons vp (cons = (cons vintrans ()))) (cons (cons vp (cons = (cons (cons vtrans (cons + (cons np (

)))) ()))) (cons (cons vintrans (cons = (cons "jumps" ()))) (cons (cons vtrans (cons = (cons "likes" ()))) (cons (cons vtrans (cons = (cons "loves" ()))) ())))))))))

) NPP (freeze true))) = true

run time: 0.0 secs

passed

passed ... 17

failed ...0

pass rate ...100%

ok

FPQi chapter 4: (load "cartprod.shen") = loadedcartesian-product

all-pairs-using-X

run time: 0.01600027084350586 secs

run time: 0.01600027084350586 secs

passed

FPQi chapter 4: (cartesian-product (cons 1 (cons 2 (cons 3 ()))) (cons 1 (cons 2 (cons 3 ())))) = [[1 1] [1 2] [1 3] [2 1] [2 2] [2 3] [3 1] [3 2] [3 3]]

run time: 0.0 secs

passed

FPQi chapter 4: (load "powerset.shen") = loadedpowerset

cons-X-to-each-set

run time: 0.0 secs

run time: 0.0 secs

passed

FPQi chapter 4: (powerset (cons 1 (cons 2 (cons 3 ())))) = [[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []]

run time: 0.0 secs

passed

passed ... 21

failed ...0

pass rate ...100%

ok

0

FPQi chapter 5: (load "bubble version 1.shen") = loadedbubble-sort

bubble

bubble-again-perhaps

run time: 0.015000343322753906 secs

run time: 0.015000343322753906 secs

passed

FPQi chapter 5: (bubble-sort (cons 1 (cons 2 (cons 3 ())))) = [3 2 1]

run time: 0.0 secs

passed

FPQi chapter 5: (load "bubble version 2.shen") = loadedbubble-sort

bubble

run time: 0.0 secs

run time: 0.0 secs

passed

FPQi chapter 5: (bubble-sort (cons 1 (cons 2 (cons 3 ())))) = [3 2 1]

run time: 0.0 secs

passed

FPQi chapter 5: (load "spreadsheet.shen") = loadedassess-spreadsheet

assign-fixed-values

assign-cell-value

fixed-value?

get'

get-row

get-cell

run time: 0.032000064849853516 secs

run time: 0.032000064849853516 secs

passed

FPQi chapter 5: (assess-spreadsheet (cons (cons jim (cons (cons wages (cons (lambda Spreadsheet (get' frank wages Spreadsheet)) ())) (cons (cons tax (cons (lambda Sp

readsheet (* (get' frank tax Spreadsheet) 0.8)) ())) ()))) (cons (cons frank (cons (cons wages (cons 20000 ())) (cons (cons tax (cons (lambda Spreadsheet (* 0.25 (ge

t' frank wages Spreadsheet))) ())) ()))) ()))) = [[jim [wages 20000] [tax 4000]] [frank [wages 20000] [tax 5000]]]

run time: 0.0 secs

passed

passed ... 27

failed ...0

pass rate ...100%

ok

9

9

FPQi chapter 3: (load "prime.shen") = loadedprime?

prime*

run time: 0.0 secs

run time: 0.0 secs

passed

FPQi chapter 3: (prime? 1000003) = true

run time: 0.49899959564208984 secs

passed

FPQi chapter 3: (load "mutual.shen") = loadedeven?

odd?

run time: 0.0 secs

run time: 0.0 secs

passed

FPQi chapter 3: (even? 56) = true

run time: 0.0 secs

passed

FPQi chapter 3: (odd? 77) = true

run time: 0.0 secs

passed

FPQi chapter 3: (load "change.shen") = loadedcount-change

count-change*

next-denom

run time: 0.0 secs

run time: 0.0 secs

passed

FPQi chapter 3: (count-change 100) = 4563

run time: 0.015000343322753906 secs

passed

passed ... 34

failed ...0

pass rate ...100%

ok

FPQi chapter 6: (load "semantic net.shen") = loadedquery

belongs?

spread-activation

accessible-from

is_links

type_links

assert

get-prop

clear

run time: 0.06299972534179688 secs

run time: 0.06299972534179688 secs

passed

FPQi chapter 6: (clear Mark_Tarver) = []

run time: 0.0 secs

passed

FPQi chapter 6: (clear man) = []

run time: 0.0 secs

passed

FPQi chapter 6: (assert (cons Mark_Tarver (cons is_a (cons man ())))) = [man]

run time: 0.0 secs

passed

FPQi chapter 6: (assert (cons man (cons type_of (cons human ())))) = [human]

run time: 0.0 secs

passed

FPQi chapter 6: (query (cons is (cons Mark_Tarver (cons human ())))) = yes

run time: 0.0 secs

passed

passed ... 40

failed ...0

pass rate ...100%

ok

FPQi chapter 7: (load "proplog version 1.shen") = loadedbackchain

backchain*

run time: 0.015000343322753906 secs

run time: 0.015000343322753906 secs

passed

FPQi chapter 7: (backchain q (cons (cons q (cons <= (cons p ()))) (cons (cons q (cons <= (cons r ()))) (cons (cons r (cons <= ())) ())))) = proved

run time: 0.0 secs

passed

FPQi chapter 7: (backchain q (cons (cons q (cons <= (cons p ()))) (cons (cons q (cons <= (cons r ()))) ()))) = ...

run time: 0.0 secs

passed

FPQi chapter 7: (load "proplog version 2.shen") = loadedbackchain

backchain*

run time: 0.03199958801269531 secs

run time: 0.03199958801269531 secs

passed

FPQi chapter 7: (backchain q (cons (cons q (cons <= (cons p ()))) (cons (cons q (cons <= (cons r ()))) (cons r ())))) = true

run time: 0.0 secs

passed

FPQi chapter 7: (backchain q (cons (cons q (cons <= (cons p ()))) (cons (cons q (cons <= (cons r ()))) ()))) = false

run time: 0.0 secs

passed

passed ... 46

failed ...0

pass rate ...100%

ok

FPQi chapter 8: (load "metaprog.shen") = loadedparse

parsed?

output_parse

generate_parser

parenthesise_rules

parenthesise_rules1

group_rules

group_rules1

place_in_group

belongs-in?

compile_rules

lex?

generate_code_for_nonlex

mapapp

get_characteristic_non_terminal

gcfn_help

apply_expansion

ae_help

generate_code_for_lex

gcfl_help

run time: 0.04699993133544922 secs

run time: 0.04699993133544922 secs

passed

FPQi chapter 8: (generate_parser (cons sent (cons --> (cons np (cons vp (cons np (cons --> (cons name (cons np (cons --> (cons det (cons n (cons name (cons --> (cons

 "John" (cons name (cons --> (cons "Bill" (cons name (cons --> (cons "Tom" (cons det (cons --> (cons "the" (cons det (cons --> (cons "a" (cons det (cons --> (cons "t

hat" (cons det (cons --> (cons "this" (cons n (cons --> (cons "girl" (cons n (cons --> (cons "ball" (cons vp (cons --> (cons vtrans (cons np (cons vp (cons --> (cons

 vintrans (cons vtrans (cons --> (cons "kicks" (cons vtrans (cons --> (cons "likes" (cons vintrans (cons --> (cons "jumps" (cons vintrans (cons --> (cons "flies" ())

))))))))))))))))))))))))))))))))))))))))))))))))))))))))) = [sent np name det n vp vtrans vintrans]

run time: 0.046000003814697266 secs

passed

passed ... 48

failed ...0

pass rate ...100%

ok

run time: 0.0 secs

passed

structures 1 - chapter 12: (ship-name (make-ship 200 "Mary Rose")) = "Mary Rose"

run time: 0.0 secs

passed

passed ... 67

failed ...0

pass rate ...100%

ok

structures 2 - chapter 12: (load "structures-typed.shen") = loadeddefstruct

selector-types

recognisor-type

constructor-type

assemble-type

defstruct

selectors

selector

constructor

params

make-association-list

recognisor

run time: 0.03099966049194336 secs

run time: 0.03099966049194336 secs

passed

structures 2 - chapter 12: (defstruct ship (cons (@p length number) (cons (@p name string) ()))) = ship

run time: 0.17199993133544922 secs

passed

structures 2 - chapter 12: (make-ship 200 "Mary Rose") = [[structure | ship] [length | 200] [name | "Mary Rose"]]

run time: 0.0 secs

passed

structures 2 - chapter 12: (ship-length (make-ship 200 "Mary Rose")) = 200

run time: 0.0 secs

passed

structures 2 - chapter 12: (ship-name (make-ship 200 "Mary Rose")) = "Mary Rose"

run time: 0.0 secs

passed

passed ... 72

failed ...0

pass rate ...100%

ok

classes 1 - chapter 12: (load "classes-untyped.shen") = loadeddefclass

make-instance

get-value

get-value-test

has-value?

has-value-test

has-attribute?

change-value

instance-of

run time: 0.29600000381469727 secs

run time: 0.29600000381469727 secs

passed

classes 1 - chapter 12: (defclass ship (cons length (cons name ()))) = ship

run time: 0.0 secs

passed

classes 1 - chapter 12: (set s (make-instance ship)) = [[class | ship] [length | fail] [name | fail]]

run time: 0.0 secs

passed

classes 1 - chapter 12: (has-value? length (value s)) = false

run time: 0.0 secs

passed

classes 1 - chapter 12: (set s (change-value (value s) length 100)) = [[class | ship] [length | 100] [name | fail]]

run time: 0.0 secs

passed

classes 1 - chapter 12: (get-value length (value s)) = 100

run time: 0.0 secs

passed

passed ... 78

failed ...0

pass rate ...100%

ok

classes 2 - chapter 12: (load "classes-typed.shen") = loadeddefclass

defclass

axiom

record-attribute-types

make-instance

make-instance

get-value

get-value

get-value-test

has-value?

has-value?

has-value-test

has-attribute?

has-attribute?

change-value

change-value

instance-of

instance-of

run time: 0.062000274658203125 secs

run time: 0.062000274658203125 secs

passed

classes 2 - chapter 12: (defclass ship (cons (@p length number) (cons (@p name string) ()))) = ship

run time: 0.07799959182739258 secs

passed

classes 2 - chapter 12: (has-value? length (make-instance ship)) = false

run time: 0.0 secs

passed

classes 2 - chapter 12: (change-value (make-instance ship) length 100) = [[class | ship] [length | 100] [name | fail]]

run time: 0.0 secs

passed

classes 2 - chapter 12: (get-value length (change-value (make-instance ship) length 100)) = 100

run time: 0.0 secs

passed

passed ... 83

failed ...0

pass rate ...100%

ok

abstract datatypes - chapter 12: (load "stack.shen") = loadedempty-stack

push

top

pop

empty-stack

push

top

pop

run time: 0.032000064849853516 secs

run time: 0.032000064849853516 secs

passed

abstract datatypes - chapter 12: (top (push 0 (empty-stack _))) = 0

run time: 0.0 secs

passed

passed ... 85

failed ...0

pass rate ...100%

ok

yacc: (load "yacc.shen") = loadedwarning: <np> <vp> has no semantics.

<sent>

warning: the has no semantics.

warning: a has no semantics.

<det>

warning: <det> <n> has no semantics.

warning: <name1> has no semantics.

<np>

warning: cat has no semantics.

warning: dog has no semantics.

<n>

<name1>

warning: <vtrans> <np> has no semantics.

<vp>

warning: likes has no semantics.

warning: chases has no semantics.

<vtrans>

<des>

warning: d <ds> has no semantics.

warning: d has no semantics.

<ds>

warning: e <es> has no semantics.

warning: e has no semantics.

<es>

<sent'>

question

<as->bs>

<find-digit>

warning: X <morestuff> has no semantics.

warning: X has no semantics.

<morestuff>

warning: 0 has no semantics.

warning: 1 has no semantics.

warning: 2 has no semantics.

warning: 3 has no semantics.

warning: 4 has no semantics.

warning: 5 has no semantics.

warning: 6 has no semantics.

warning: 7 has no semantics.

warning: 8 has no semantics.

warning: 9 has no semantics.

<digit>

warning: <digit> <morestuff> has no semantics.

<find-digit'>

warning: <as> <bs> <cs> has no semantics.

<asbscs>

warning: a <as> has no semantics.

warning: a has no semantics.

<as>

warning: b <bs> has no semantics.

warning: b has no semantics.

warning: <e> has no semantics.

<bs>

warning: c <cs> has no semantics.

warning: c has no semantics.

<cs>

warning: <as> <bs'> <cs> has no semantics.

<asbs'cs>

warning: b <bs'> has no semantics.

warning: b has no semantics.

warning: <e> has no semantics.

<bs'>

<find-digit''>

<digit''>

<anbncn>

warning: a <as> has no semantics.

warning: a has no semantics.

<as>

warning: b <bs> has no semantics.

warning: b has no semantics.

<bs>

warning: c <cs> has no semantics.

warning: c has no semantics.

<cs>

equal-length?

appendall

<a*s>

warning: [cons b []] b has no semantics.

<b*>

warning: c has no semantics.

<c*>

<d*>

run time: 0.24900007247924805 secs

run time: 0.24900007247924805 secs

passed

yacc: (compile (function <sent>) (cons the (cons cat (cons likes (cons the (cons dog ()))))) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.app

 E "

" shen.s))) (simple-error "parse error

")))) = [the cat likes the dog]

run time: 0.0 secs

passed

yacc: (compile (function <sent>) (cons the (cons cat (cons likes (cons the (cons canary ()))))) (lambda E (fail))) = ...

run time: 0.0 secs

passed

yacc: (compile (function <asbscs>) (cons a (cons a (cons a (cons b (cons b (cons c ())))))) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.app

E "

" shen.s))) (simple-error "parse error

")))) = [a a a b b c]

run time: 0.0 secs

passed

yacc: (compile (function <find-digit>) (cons a (cons v (cons f (cons g (cons 6 (cons y (cons u ()))))))) (lambda E (if (cons? E) (simple-error (cn "parse error here:

 " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [6]

run time: 0.0 secs

passed

yacc: (compile (function <vp>) (cons chases (cons the (cons cat ()))) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [chases the cat]

run time: 0.0 secs

passed

yacc: (compile (function <des>) (cons (cons d ()) (cons (cons e (cons e ())) ())) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [d e e]

run time: 0.0 secs

passed

yacc: (compile (function <sent'>) (cons the (cons cat (cons likes (cons the (cons dog ()))))) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.ap

p E "

" shen.s))) (simple-error "parse error

")))) = [is it true that your father likes the dog ?]

run time: 0.0 secs

passed

yacc: (compile (function <as>) (cons a (cons a (cons a ()))) (lambda E (if (cons? E) (simple-error (cn "parse error here: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [a a a]

run time: 0.0 secs

passed

yacc: (compile (function <find-digit'>) (cons a (cons v (cons f (cons g (cons 6 (cons y (cons u ()))))))) (lambda E (if (cons? E) (simple-error (cn "parse error here

: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [6 y u]

run time: 0.0 secs

passed

yacc: (compile (function <asbs'cs>) (cons a (cons v (cons f (cons g (cons 6 (cons y (cons u ()))))))) (lambda E (fail))) = ...

run time: 0.0 secs

passed

yacc: (compile (function <find-digit''>) (cons a (cons v (cons f (cons g (cons 6 (cons y (cons u ()))))))) (lambda E (if (cons? E) (simple-error (cn "parse error her

e: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = 6

run time: 0.0 secs

passed

yacc: (compile (function <anbncn>) (cons a (cons a (cons a (cons b (cons b (cons b (cons c (cons c (cons c ()))))))))) (lambda E (if (cons? E) (simple-error (cn "par

se error here: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [a a a b b b c c c]

run time: 0.0 secs

passed

passed ... 98

failed ...0

pass rate ...100%

ok

yacc: (compile (function <anbncn>) (cons a (cons a (cons a (cons b (cons b (cons b (cons c (cons c (cons c ()))))))))) (lambda E (if (cons? E) (simple-error (cn "par

se error here: " (shen.app E "

" shen.s))) (simple-error "parse error

")))) = [a a a b b b c c c]

run time: 0.0 secs

passed

passed ... 98

failed ...0

pass rate ...100%

ok

h

h

[]

true

N Queens: (preclude-all-but ()) = []

run time: 0.0 secs

passed

N Queens: (tc +) = true

run time: 0.0 secs

passed

N Queens: (load "n queens.shen") = loaded

n-queens : (number --> (list (list number)))

initialise : (number --> (list number))

n-queens-loop : (number --> ((list number) --> (list (list number))))

all_Ns? : (number --> ((list number) --> boolean))

next_n : (number --> ((list number) --> (list number)))

ok_row? : ((list number) --> boolean)

ok_diag? : ((list number) --> boolean)

ok_diag_N? : (number --> (number --> ((list number) --> boolean)))

run time: 0.07800006866455078 secs

typechecked in 115536 inferences

run time: 0.07800006866455078 secs

passed

N Queens: (n-queens 5) = [[4 2 5 3 1] [3 5 2 4 1] [5 3 1 4 2] [4 1 3 5 2] [5 2 4 1 3] [1 4 2 5 3] [2 5 3 1 4] [1 3 5 2 4] [3 1 4 2 5] [2 4 1 3 5]]

run time: 0.0 secs

passed

N Queens: (tc -) = false

run time: 0.0 secs

passed

passed ... 103

failed ...0

pass rate ...100%

ok

search: (tc +) = true

run time: 0.0 secs

passed

search: (load "search.shen") = loaded

breadth-first : (state --> ((state --> (list state)) --> ((state --> boolean) --> boolean)))

b* : ((state --> (list state)) --> ((state --> boolean) --> ((list state) --> boolean)))

some : ((A --> boolean) --> ((list A) --> boolean))

depth : (state --> ((state --> (list state)) --> ((state --> boolean) --> boolean)))

d* : ((state --> (list state)) --> ((state --> boolean) --> ((list state) --> boolean)))

hill : ((state --> number) --> (state --> ((state --> (list state)) --> ((state --> boolean) --> boolean))))

h* : ((state --> number) --> ((state --> (list state)) --> ((state --> boolean) --> ((list state) --> boolean))))

order_states : ((state --> number) --> ((list state) --> (list state)))

sort : ((A --> (A --> boolean)) --> ((list A) --> (list A)))

sort* : ((A --> (A --> boolean)) --> ((list A) --> (list A)))

run time: 0.1400003433227539 secs

typechecked in 119542 inferences

run time: 0.1400003433227539 secs

passed

search: (tc -) = false

run time: 0.0 secs

passed

passed ... 106

failed ...0

pass rate ...100%

ok

whist - chapter 11: (tc +) = true

run time: 0.0 secs

passed

whist - chapter 11: (load "whist.shen") = loaded

type#rank : symbol

type#suit : symbol

type#lead : symbol

whist : (lead --> string)

deck : (A --> (list (rank * suit)))

cartprod : ((list A) --> ((list B) --> (list (A * B))))

deal-whist : (number --> ((list (rank * suit)) --> (((list (rank * suit)) * (list (rank * suit))) --> ((list (rank * suit)) * (list (rank * suit))))))

deal-card : ((list (rank * suit)) --> (rank * suit))

random : (A --> A)

whist-loop : (((list (rank * suit)) * (list (rank * suit))) --> (number --> (number --> (lead --> string))))

determine-legal : ((rank * suit) --> ((rank * suit) --> ((list (rank * suit)) --> (rank * suit))))

legal? : ((rank * suit) --> ((rank * suit) --> ((list (rank * suit)) --> boolean)))

void-of-suit? : (suit --> ((list (rank * suit)) --> boolean))

same-suit : ((list (rank * suit)) --> (suit --> (list (rank * suit))))

determine-winner : ((rank * suit) --> ((rank * suit) --> (lead --> lead)))

return-winner : (lead --> lead)

game-over? : (((list (rank * suit)) * (list (rank * suit))) --> boolean)

play-computer-lead : ((list (rank * suit)) --> (rank * suit))

computer-shows : ((rank * suit) --> (rank * suit))

map-rank : (rank --> string)

map-suit : (suit --> string)

select-highest : ((list (rank * suit)) --> (rank * suit))

select-highest-help : ((rank * suit) --> ((list (rank * suit)) --> (rank * suit)))

higher? : ((rank * suit) --> ((rank * suit) --> boolean))

play-computer-follow : ((list (rank * suit)) --> ((rank * suit) --> (rank * suit)))

sort : ((A --> (A --> boolean)) --> ((list A) --> (list A)))

sort-help : ((A --> (A --> boolean)) --> ((list A) --> (list A)))

select-higher : ((rank * suit) --> ((list (rank * suit)) --> (rank * suit)))

select-lowest : ((list (rank * suit)) --> (rank * suit))

select-lowest-help : ((rank * suit) --> ((list (rank * suit)) --> (rank * suit)))

lower? : ((rank * suit) --> ((rank * suit) --> boolean))

play-player : ((list (rank * suit)) --> (rank * suit))

show-cards : (number --> ((list (rank * suit)) --> string))

in-range? : (number --> ((list (rank * suit)) --> boolean))

run time: 0.5299997329711914 secs

typechecked in 131999 inferences

run time: 0.5299997329711914 secs

passed

whist - chapter 11: (tc -) = false

run time: 0.0 secs

passed

passed ... 109

failed ...0

pass rate ...100%

ok

Qi interpreter - chapter 13: (tc +) = true

run time: 0.0 secs

passed

Qi interpreter - chapter 13: (load "interpreter.shen") = loaded

type#num : symbol

type#primitive_object : symbol

type#pattern : symbol

type#l_formula : symbol

l_interpreter : (A --> B)

read_eval_print_loop : (string --> A)

normal_form : (l_formula --> l_formula)

==>> : (l_formula --> l_formula)

eval_error? : (l_formula --> boolean)

successor : (A --> l_formula)

predecessor : (A --> l_formula)

sub : ((list (pattern * l_formula)) --> (l_formula --> l_formula))

match : (pattern --> (l_formula --> (list (pattern * l_formula))))

no_match? : ((list (pattern * l_formula)) --> boolean)

replace : (pattern --> (l_formula --> (l_formula --> l_formula)))

free? : (pattern --> (pattern --> boolean))

run time: 1.7320003509521484 secs

typechecked in 428017 inferences

run time: 1.7320003509521484 secs

passed

Qi interpreter - chapter 13: (tc -) = false

run time: 0.0 secs

passed

passed ... 112

failed ...0

pass rate ...100%

ok

proof assistant - chapter 15: (tc +) = true

run time: 0.0 secs

passed

proof assistant - chapter 15: (load "proof assistant.shen") = loaded

type#globals : symbol

proof-assistant : (A --> symbol)

input-assumptions : (number --> (list wff))

input-conclusion : (A --> wff)

proof-loop : ((list ((list wff) * wff)) --> ((list ((list ((list wff) * wff)) * ((list ((list wff) * wff)) --> (list ((list wff) * wff))))) --> (list ((list ((list w

ff) * wff)) * ((list ((list wff) * wff)) --> (list ((list wff) * wff)))))))

show-proof : (string --> symbol)

show-proof-help : ((list ((list ((list wff) * wff)) * ((list ((list wff) * wff)) --> (list ((list wff) * wff))))) --> (number --> symbol))

show-sequent : ((list ((list wff) * wff)) --> (number --> symbol))

enumerate : ((list A) --> (number --> symbol))

user-directive : (A --> ((list ((list wff) * wff)) --> (list ((list wff) * wff))))

back : ((list ((list wff) * wff)) --> (list ((list wff) * wff)))

go-back : ((list ((list ((list wff) * wff)) * ((list ((list wff) * wff)) --> (list ((list wff) * wff))))) --> (list ((list wff) * wff)))

run time: 0.3899993896484375 secs

typechecked in 432352 inferences

run time: 0.3899993896484375 secs

passed

proof assistant - chapter 15: (tc -) = false

run time: 0.0 secs

passed

passed ... 115

failed ...0

pass rate ...100%

ok

quantifier machine: (tc +) = true

run time: 0.0 secs

passed

quantifier machine: (load "qmachine.shen") = loadedwarning: changing the type of push may create errors

type#progression : symbol

force : ((progression A) --> A)

delay : ((progression A) --> (progression A))

end? : ((progression A) --> boolean)

push : (A --> ((progression A) --> (progression A)))

forall : ((progression A) --> ((A --> boolean) --> boolean))

exists : ((progression A) --> ((A --> boolean) --> boolean))

super : ((progression A) --> ((A --> B) --> ((B --> (C --> C)) --> (C --> C))))

forall : ((progression A) --> ((A --> boolean) --> boolean))

exists : ((progression A) --> ((A --> boolean) --> boolean))

for : ((progression A) --> ((A --> B) --> number))

progn : (A --> (B --> B))

filter : ((progression A) --> ((A --> boolean) --> (list A)))

next-prime : (number --> number)

prime? : (number --> boolean)

prime-help : (number --> (number --> (number --> boolean)))

run time: 0.49899959564208984 secs

typechecked in 436239 inferences

run time: 0.49899959564208984 secs

passed

quantifier machine: (exists (cons 1 (cons (+ 1) (cons (= 100) ()))) (> 50)) = true

run time: 0.0 secs

passed

quantifier machine: (tc -) = false

run time: 0.0 secs

passed

passed ... 119

failed ...0

pass rate ...100%

ok

depth first search: (tc +) = true

run time: 0.0 secs

passed

depth first search: (load "depth'.shen") = loaded

depth' : (A --> ((A --> (list A)) --> ((A --> boolean) --> ((A --> boolean) --> (list A)))))

depth-help' : ((list A) --> ((A --> (list A)) --> ((A --> boolean) --> ((A --> boolean) --> ((list A) --> (list A))))))

run time: 0.04699993133544922 secs

typechecked in 437892 inferences

run time: 0.04699993133544922 secs

passed

depth first search: (depth' 4 (lambda X (cons (+ X 3) (cons (+ X 4) (cons (+ X 5) ())))) (lambda X (= X 27)) (lambda X (> X 27))) = [4 7 10 13 16 19 22 27]

run time: 0.0 secs

passed

depth first search: (depth' 4 (lambda X (cons (+ X 3) ())) (lambda X (= X 27)) (lambda X (> X 27))) = []

run time: 0.0 secs

passed

depth first search: (tc -) = false

run time: 0.0 secs

passed

passed ... 124

failed ...0

pass rate ...100%

ok

Lisp type checker: (load "TinyTypes.shen") = loadeddefun

lambda'

type#tiny_lisp_type_theory

mk_lambda

run time: 0.29600048065185547 secs

run time: 0.29600048065185547 secs

passed

Lisp type checker: (tc +) = true

run time: 0.0 secs

passed

Lisp type checker: (load "TinyLispFunctions.txt") = loaded

plus : (number --> (number --> number))

member : (A --> ((list A) --> (list A)))

join : ((list A) --> ((list A) --> (list A)))

run time: 0.015999794006347656 secs

typechecked in 439247 inferences

run time: 0.015999794006347656 secs

passed

Lisp type checker: (tc -) = false

run time: 0.0 secs

passed

passed ... 128

failed ...0

pass rate ...100%

ok

0

run time: 7.565999984741211 secs

loaded

(4-)

[Mark Tarver]

A couple of lines stick out

SBCL/Shen Prolog Einstein's Riddle 0.07799959182739258 secs

F#/Shen Prolog Einstein's Riddle 12.0338178 secs

Suggests there is a bottleneck in the Prolog.

SBCL/Shen FPQi chapter 3: (prime? 1000003) = true run time: 0.49899959564208984 secs

F#/Shen FPQi chapter 3: (prime? 1000003) = true run time: 16.0707698 secs

Keep going btw;  I had to optimise Shen during 2011 to get performance.  Does anybody know how F# compares to SBCL?

Mark

[Bruno Deferrari]

F# is fast, but note that right now Robert's implementation is an interpreter, he doesn't generate F# code.

An interpreter for KLambda code will never be as fast as SBCL running KLambda code that has been compiled into Common Lisp, but should be able to reach speed comparable to the Ruby and Scheme ports.

I don't know how well runtime code generation and execution works in .NET, but doing so one may be able to reach SBCL levels of performance (but it is more work). In any case, even if runtime code generation (or just generating F# code for offline compilation) is part of Robert's plan, I think he did the right thing by starting with an interpreter (unlike him, I started from the other side when working on the OCaml port, turns out that approach is much harder when targeting statically typed languages).

Anyway I think there is plenty of space for performance improvements in that interpreter, just taking care of system functions already made a big change, and I think improving function lookups (like I described in the other mail, or any other way) will result in a big speedup.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[deech]

If you need a datapoint for an interpreted port my elisp port (https://github.com/deech/shen-elisp) goes through the test in 40-43 seconds..

My machine specs are:
Quad core Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
16GB RAM.

-deech

On Wednesday, February 15, 2017 at 6:24:34 PM UTC-6, Bruno Deferrari wrote:

F# is fast, but note that right now Robert's implementation is an interpreter, he doesn't generate F# code.

An interpreter for KLambda code will never be as fast as SBCL running KLambda code that has been compiled into Common Lisp, but should be able to reach speed comparable to the Ruby and Scheme ports.

I don't know how well runtime code generation and execution works in .NET, but doing so one may be able to reach SBCL levels of performance (but it is more work). In any case, even if runtime code generation (or just generating F# code for offline compilation) is part of Robert's plan, I think he did the right thing by starting with an interpreter (unlike him, I started from the other side when working on the OCaml port, turns out that approach is much harder when targeting statically typed languages).

Anyway I think there is plenty of space for performance improvements in that interpreter, just taking care of system functions already made a big change, and I think improving function lookups (like I described in the other mail, or any other way) will result in a big speedup.

On Wed, Feb 15, 2017 at 8:27 PM, Mark Tarver <dr.mt...@gmail.com> wrote:

A couple of lines stick out

SBCL/Shen Prolog Einstein's Riddle 0.07799959182739258 secs

F#/Shen Prolog Einstein's Riddle 12.0338178 secs

Suggests there is a bottleneck in the Prolog.

SBCL/Shen FPQi chapter 3: (prime? 1000003) = true run time: 0.49899959564208984 secs

F#/Shen FPQi chapter 3: (prime? 1000003) = true run time: 16.0707698 secs

Keep going btw;  I had to optimise Shen during 2011 to get performance.  Does anybody know how F# compares to SBCL?

Mark

--
You received this message because you are subscribed to the Google Groups "Shen" group.

To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.

To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Bruno Deferrari]

On Wed, Feb 15, 2017 at 9:53 PM, deech <aditya...@gmail.com> wrote:

If you need a datapoint for an interpreted port my elisp port (https://github.com/deech/shen-elisp) goes through the test in 40-43 seconds..

My machine specs are:
Quad core Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz
16GB RAM.

Here are my times for reference:

Computer: 2.4 GHz Intel Core i5, 8GB RAM

Scheme port running on chibi:       30.x seconds

Ruby port running on ruby 2.4.0:    20.x seconds

Scheme port running on of Gauche:   10.x seconds

Common Lisp port running on SBCL:    6.x seconds

Couldn't run the tests with CLisp, it segfaults on my computer when running the tests and I don't know why (sometimes I upgrade CLisp and it gets fixed, but it didn't do the trick now).

The Scheme port uses mostly the same code for both Gauche and chibi, but Gauche is a more performant implementation (while still not generating machine code at runtime).

 

To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.

To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Robert Koeninger]

The link for the port is just the GitHub page: https://github.com/rkoeninger/ShenSharp.

It's BSD 3-clause licensed.

You can use rkoeninger (at) att.net as my contact e-mail.

To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.

To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

--
You received this message because you are subscribed to the Google Groups "Shen" group.

To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.

[Robert Koeninger]

Mark, deech, Bruno, thanks for the benchmark comparisons, looks like I have some work to do.

[Robert Koeninger]

Bruno, I had a few ideas for improving function lookups informed by your suggestions:

    * When a defun is defined, uses of global functions can be replaced with a lazily created mutable reference cell (SymbolRef) so that point in the code will always have a direct reference to the function

      Instead of Globals being a pair of Dictionaries for symbols and functions, instead you'd have:

            type Globals = Dictionary<string, SymbolRef>

            type SymbolRef = string * Value option ref * Function option ref

    * Uses of (value symbol) and (set symbol value), if the symbol is global and not a local variable, can be replaced with direct references to SymbolRefs that contain the optionally defined value for that symbol.

    * When lambda and freeze expressions are evaluated and an interpreted lambda or freeze value is created, instead of including the entire local scope, uses of local variables in the captured scope and be immediately replaced with their current values as local bindings are immutable.

    * This would also allow idle symbols to be identified without a lookup

This would result in the introduction of an additional data type to represent optimized syntax trees, which is a bit amusing, because I just removed the concept of separate data types for parsed trees, expression trees and values back in January, for the sake of simplicity.

On Wednesday, February 15, 2017 at 7:24:34 PM UTC-5, Bruno Deferrari wrote:

...

[Bruno Deferrari]

Yes, what you have in mind would be even better :)

The approach I suggested was intended to be a not-too-invasive change (the interpreter mechanisms would stay the same, it was just lookups that would be changed by switching from strings to a new datatype).

But if you can implement what you describe here without complicating your life much, the performance gains should be greater.

Regarding your SymbolRef type, what if instead of a Function option ref you just use a Function ref, with a default Function value that just throws an undefined function error? that should save you the time (and code) of having to check for None values.

let raise_undefined_function name =

   ... (* build Function value that raises an exception 

          with msg = "Function not defined: %s" name *)

These would only be created when at the time of creating the reference the function doesn't exist yet.

On another topic...

Note that (in current versions of Shen, this wasn't true in the past) you don't have to support code like this:

(let X + (X 1 2))

being that the correct, portable way to write this code is:

(let X (function +) (X 1 2))

`function` is a macro defined at the Shen level (it results in an inlined lambda expression with nesting equal to the arity of the function being passed to it), nothing that you have to handle yourself (at least not in newer versions of Shen).

(function +) becomes (lambda X (lambda Y (+ X Y)))

What this means is that whenever you have a function application expression, you only have to check that the operand is a function/lambda and apply it, otherwise you can throw an error, no need to do a lookup if it is a symbol value.

I mention this because it may affect how you decide to represent your globals/symbols/functions knowing that they are disjoint and that you will not have the need to go from a symbol to a function at code execution time (only during compilation). May also let you simplify your evaluator logic a bit.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Mark Tarver]

No probs;  I didn't know it was an interpreter you had.  Makes a big difference.

Mark

On Fri, Feb 17, 2017 at 4:10 AM, Robert Koeninger <robertk...@gmail.com> wrote:

Mark, deech, Bruno, thanks for the benchmark comparisons, looks like I have some work to do.

--

[Bruno Deferrari]

On Fri, Feb 17, 2017 at 6:03 AM, Bruno Deferrari <uti...@gmail.com> wrote:

Yes, what you have in mind would be even better :)

The approach I suggested was intended to be a not-too-invasive change (the interpreter mechanisms would stay the same, it was just lookups that would be changed by switching from strings to a new datatype).

But if you can implement what you describe here without complicating your life much, the performance gains should be greater.

Regarding your SymbolRef type, what if instead of a Function option ref you just use a Function ref, with a default Function value that just throws an undefined function error? that should save you the time (and code) of having to check for None values.

let raise_undefined_function name =

   ... (* build Function value that raises an exception 

          with msg = "Function not defined: %s" name *)

These would only be created when at the time of creating the reference the function doesn't exist yet.

On another topic...

Note that (in current versions of Shen, this wasn't true in the past) you don't have to support code like this:

(let X + (X 1 2))

being that the correct, portable way to write this code is:

(let X (function +) (X 1 2))

`function` is a macro defined at the Shen level (it results in an inlined lambda expression with nesting equal to the arity of the function being passed to it), nothing that you have to handle yourself (at least not in newer versions of Shen).

(function +) becomes (lambda X (lambda Y (+ X Y)))

What this means is that whenever you have a function application expression, you only have to check that the operand is a function/lambda and apply it, otherwise you can throw an error, no need to do a lookup if it is a symbol value.

I mention this because it may affect how you decide to represent your globals/symbols/functions knowing that they are disjoint and that you will not have the need to go from a symbol to a function at code execution time (only during compilation). May also let you simplify your evaluator logic a bit.

To expand a bit on this, this code works, but nothing has to be done by the port writer for it to work:

((let X + (function X)) 1 2)

(the result is 3)

This works because in addition to the `function` macro, Shen also defines a `function` function. When a function is being compiled from Shen to Kl, a reference to the callable function is stored in a table. That table is used by the function version of `function` to do symbol->function lookups.

So, if the symbol is known at read time (it is a literal symbol and not a variable), the macro takes care of it, otherwise the function version of `function` will do the job.

Example:

(0-) (hd (read-from-string "((function +) 1 2)"))
[[lambda V1222 [lambda V1223 [+ V1222 V1223]]] 1 2]

(1-) (hd (read-from-string "(let X + ((function X) 1 2))"))
[let X + [[function X] 1 2]]

Just wanted to clarify this because from my previous message you could get the impression that you wouldn't be able to get a function from a symbol at runtime if you don't write support for it in your port.

On Fri, Feb 17, 2017 at 1:39 AM, Robert Koeninger <robertk...@gmail.com> wrote:

Bruno, I had a few ideas for improving function lookups informed by your suggestions:

    * When a defun is defined, uses of global functions can be replaced with a lazily created mutable reference cell (SymbolRef) so that point in the code will always have a direct reference to the function

      Instead of Globals being a pair of Dictionaries for symbols and functions, instead you'd have:

            type Globals = Dictionary<string, SymbolRef>

            type SymbolRef = string * Value option ref * Function option ref

    * Uses of (value symbol) and (set symbol value), if the symbol is global and not a local variable, can be replaced with direct references to SymbolRefs that contain the optionally defined value for that symbol.

    * When lambda and freeze expressions are evaluated and an interpreted lambda or freeze value is created, instead of including the entire local scope, uses of local variables in the captured scope and be immediately replaced with their current values as local bindings are immutable.

    * This would also allow idle symbols to be identified without a lookup

This would result in the introduction of an additional data type to represent optimized syntax trees, which is a bit amusing, because I just removed the concept of separate data types for parsed trees, expression trees and values back in January, for the sake of simplicity.

On Wednesday, February 15, 2017 at 7:24:34 PM UTC-5, Bruno Deferrari wrote:

...

Anyway I think there is plenty of space for performance improvements in that interpreter, just taking care of system functions already made a big change, and I think improving function lookups (like I described in the other mail, or any other way) will result in a big speedup.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

--

BD

[Robert Koeninger]

Further performance improvement by employing some of Bruno's suggestions. Standard test suite now runs in 75 seconds. 142mins (a month ago) -> 12mins (a couple weeks ago) -> 1.25mins.

So instead of just evaluating the syntax tree each time a function is applied, syntax trees are parsed into optimized expression trees that hold onto global, mutable references that hold a global function or symbol. This way, calling non-local user-defined functions can be done without a lookup, as can (set symbol Expr) and (value symbol), so long as the symbols are not local variables or the product of evaluating another expression.

Next, I'm going to try looking up local variables in integer-indexed lists/arrays and pre-populating captured scope into expression trees instead of looking up the local values in captured scope each call.

Unless anyone has any ideas about what might be more helpful.

[deech]

Have you tried peephole optimizing? I got a lot of mileage out of encoding 'map' , hash table functions (get, put etc.) and string operations in the host language.

[Bruno Deferrari]

This + peephole optimizations as Aditya suggested would be the next things in the list IMO.

Here is the file where I add my own overwrites for the Scheme port (iirc replacing functions like `map` with the native ones didn't make much of a difference for me, but may do for you, so you should give those a try):

https://github.com/tizoc/shen-scheme/blob/master/overwrites.shen

`hash` in particular is a very easy one to overwrite that will give you good performance gains, because Shen's implementation of a hashing function will never be able to compile with the native one.

Aditya, which ones have worked well for you?

 

Unless anyone has any ideas about what might be more helpful.

--

You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+unsubscribe@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[deech]

Another route is since you now have a working interpreter, use it to read KLambda sources and spit out F#; the idea is to compile when you can and interpret the rest.

[deech]

I would say I got my biggest peep-hole perf. boosts with https://github.com/deech/shen-elisp/blob/master/shen-elisp.org#overrides and https://github.com/deech/shen-elisp/blob/master/shen-elisp.org#hash-table. I also did a number of other things like turning '(cdr (cdr (cdr ..)))' into '(nthcdr 2 ..)' and so on.
-deech

On Thursday, February 23, 2017 at 7:11:49 PM UTC-6, Bruno Deferrari wrote:

On Thu, Feb 23, 2017 at 9:21 PM, Robert Koeninger <robertk...@gmail.com> wrote:

Further performance improvement by employing some of Bruno's suggestions. Standard test suite now runs in 75 seconds. 142mins (a month ago) -> 12mins (a couple weeks ago) -> 1.25mins.

So instead of just evaluating the syntax tree each time a function is applied, syntax trees are parsed into optimized expression trees that hold onto global, mutable references that hold a global function or symbol. This way, calling non-local user-defined functions can be done without a lookup, as can (set symbol Expr) and (value symbol), so long as the symbols are not local variables or the product of evaluating another expression.

Next, I'm going to try looking up local variables in integer-indexed lists/arrays and pre-populating captured scope into expression trees instead of looking up the local values in captured scope each call.

This + peephole optimizations as Aditya suggested would be the next things in the list IMO.

Here is the file where I add my own overwrites for the Scheme port (iirc replacing functions like `map` with the native ones didn't make much of a difference for me, but may do for you, so you should give those a try):

https://github.com/tizoc/shen-scheme/blob/master/overwrites.shen

`hash` in particular is a very easy one to overwrite that will give you good performance gains, because Shen's implementation of a hashing function will never be able to compile with the native one.

Aditya, which ones have worked well for you?

 

Unless anyone has any ideas about what might be more helpful.

--
You received this message because you are subscribed to the Google Groups "Shen" group.

To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.

To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

--

BD

[Robert Koeninger]

Got a NuGet package published, including the REPL as a command line program (tools/Shen.exe) and the runtime as an embed-able library (lib/net45/Shen.lib).

I don't think there are many .Net people here, but there is a download link on the left. Even if you're not on Windows, you can still run it using Mono (worked for me in my Ubuntu VM).

If you do have Visual Studio, you can start a new project and add it as a NuGet dependency as usual.

[Robert Koeninger]

I tried a peephole optimization for shen.mod, which seems like a good one to optimize as modulus is a basic operator in the native language, but it didn't noticeably help. Maybe if I replaced several functions with native ones, it would add up.

I added captured scope inlining - when a lambda/freeze is evaluated and a lambda/freeze value is created, the syntax tree is rebuilt and local variables from the containing scope are replaced with their captured value - but that didn't noticeably speed anything up. I thought it would help since a closure might be created and then used repeatedly.