2018/03/05

Generalized setter inlining

(This is a continuation of Procedure inliner improvement.)

Another improvement of procedure inlining in 0.9.6 is about generalized setters.

Generalized setter srfi:17 allows set! to behave as if it takes lvalue of the first argument.

gosh> (define p (list (vector 1)))
p
gosh> p
(#(1))
gosh> (set! (vector-ref (car p) 0) 2)
#<undef>
gosh> p
(#(2))

It isn't really calculating lvalue of (vector-ref (car p) 0). The trick is a very simple conversion:

(set! (fn arg ...) value)
  ↓
((setter fn) arg ... value)

If fn is known at the compile time, and (setter fn) is a constant binding, the compiler can inline the value of (setter fn). In the following example, you see the compiler knows (setter vector-ref) is vector-set!, and emit the VM instruction instead of making a procedure call:

gosh> (disasm (^[] (set! (vector-ref (car p) 0) 2)))
CLOSURE #<closure (#f)>
=== main_code (name=#f, code=0x2939600, size=6, const=1 stack=1):
signatureInfo: ((#f))
     0 GREF #<identifier user#p.2629740>; p
     2 CAR-PUSH                 ; (car p)
     3 CONSTI(2) 
     4 VEC-SETI(0)              ; ((setter vector-ref) (car p) 0 2)
     5 RET 

This is exactly the same code as (vector-set! (car p) 0 2).

Actually, srfi-17 is written with this optimization in mind. The ref:getter-with-setter procedure is specified to bind an accessor and a mutator in immutable way, so that the compiler can safely replace (setter fn) form with fn's mutator. It's just that we haven't taken advantage of it until now.

Since we have this optimization now, it is less important to have separate mutator procedure than accessor---you can attach the mutator as the setter of the accessor, and without penalty you can use set! to invoke the mutator.

Tags: 0.9.6, Compiler, srfi-17

2018/03/04

Procedure inliner improvement

This is about the compiler internal change in 0.9.6. There's no user-visible changes; it might be interesting if you're curious about compiler internals.

＊ ＊ ＊

Some of Gauche's primitive procedures are inlined as VM instructions. For example, Gauche's VM has an instruction to reference an element of a vector with immediate offset. If vector-ref's second argument is a constant, the instruction is used:

gosh> (disasm (^x (vector-ref x 0)))
CLOSURE #<closure (#f x)>
=== main_code (name=#f, code=0x20e3160, size=3, const=0 stack=0):
signatureInfo: ((#f x))
     0 LREF0                    ; x
     1 VEC-REFI(0)              ; (vector-ref x 0)
     2 RET 

This tends to be pretty effective in performance.

You can also define a procedure as inlinable, using define-inline. We've been using it to optimize Gauche runtime.

However, up to 0.9.5, inlining is limited only when the inlinable procedure appears at the procedure position of the function application. In the following example, vector-ref wasn't inlined because it does not appear literally at the procedure position:

gosh> (define-inline (foo ref) (^x (ref x 0)))
foo
gosh> (disasm (^x ((foo vector-ref) x)))
CLOSURE #<closure (#f x)>
=== main_code (name=#f, code=0x2228f50, size=9, const=2 stack=14):
signatureInfo: ((#f x))
     0 LREF0-PUSH               ; x
     1 PRE-CALL(1) 7            ; (foo vector-ref)
     3 GREF-PUSH #<identifier user#vector-ref.2238300>; vector-ref
     5 GREF-CALL(1) #<identifier user#foo.2238340>; (foo vector-ref)
     7 TAIL-CALL(1)             ; ((foo vector-ref) x)
     8 RET 

It's been bothering us, since it is natural to expect that the effect of inlining and β-reduction cascades as follows:

((foo vector-ref) v)
 ↓
(((^[ref] (^x (ref x 0))) vector-ref) v)
 ↓
((^x (vector-ref x 0)) v)
 ↓
(vector-ref v 0)

It was the old inline interface that prevented this.

＊ ＊ ＊

Gauche's compiler has 5 passes. Pass 1 expands macros and replaces input S expressions into a graph called IForm. Pass 2-4 works on IForm to optimize, and pass 5 walks final IForm to emit VM instructions.

It is pass 1 where vector-ref was expanded. Inlinable procedures have an attached inliner procedure, which takes an input S expression and compile-time environment Cenv, and returns expanded IForm:

    Inliner :: Sexpr, Cenv -> IForm

When the compiler see a form (fn arg ...) and fn has an inliner, the form (fn arg ...) is passed to it and the returned IForm becomes the result of pass1 of the original form.

If fn is defined with define-inline, the inliner procedure is a closure that keeps IForm of the original procedure. If the compiler sees this definition:

    (define-inline (vref v) (vector-ref v 0))

We process (v (vector-ref v 0)) with pass 1 and obtain its IForm. Let's denote it as #<IForm (^v (vector-ref v 0))> for now. The inliner of vref would be something like this:

    (^[sexpr cenv]
      (#Apply #<IForm (^v (vector-ref v 0))>
              (map (cut pass1 <> cenv) (cdr sexpr))))

Here, the pseudo function "#Apply" builds an IForm that applies the first argument on the list of IForms in the second argument. The subsequent optimization passes would eliminate binding of local variable v if possible.

We could've kept the body of vref in S-expression and just expand it much like legacy macro expansion:

    (^[sexpr cenv]
      (pass1 `(apply (^v (vector-ref v 0)) ,@(cdr sexpr)) cenv))

But such way would run into the hygiene problem. We have to rename vector-ref to avoid potential name conflict. Running through pass1 resolves all the identifier references, hence it addresses hygiene issue as well.

The problem is that the inliner's input is Sexpr and output is IForm. that means we can't apply an inliner on the result of another inliner. It was the reason that the foo case above didn't inlined as expected.

There are also other opportunities of inlining during pass 3. Once we do closure optimization and redundant local variable elimination, we might get a procedure call where the procedure has attached inliner. Since we're working on IForm in pass 3, we couldn't apply inliners in such case.

＊ ＊ ＊

The solution is to change inliner protocol. Instead of taking input Sexpr, we can make the inliner takes IForms:

   Inliner :: IForm, [IForm] -> IForm

The first IForm is the body of inlinable procedure, and the second list of IForms are the IForm from argument expressions. The information of Cenv is already folded in IForm.

In pass 1, we process the procedure and the argument with pass1 before calling the inliner. In pass 3 we can just call the inliner.

Now the effect of inlining cascades.

;; Returns a procedure that takes the first element of the given sequence,
;; using REF as the accessor.
(define-inline (foo ref)
  (^v (ref v 0)))

;; Returns accessor accoring to the symbol TYPE.
(define-inline (bar type) 
  (cond 
   [(eq? type 'v) vector-ref]
   [(eq? type 'u8) u8vector-ref]))

;; Using foo and bar to access the first element of V, using an accessor
;; designated by TYPE:
(define-inline (baz type v)
  (let ((ref (bar type)))
    ((foo ref) v)))

If type is constant, the cond expression in bar is computed at the compile time, allowing that we inline everything down to a VM instruction:

gosh> (disasm (^v (baz 'v v)))
CLOSURE #<closure (#f v)>
=== main_code (name=#f, code=0x28783e0, size=3, const=0 stack=0):
signatureInfo: ((#f v))
     0 LREF0                    ; v
     1 VEC-REFI(0)              ; (ref v 0)
     2 RET 
gosh> (disasm (^v (baz 'u8 v)))
CLOSURE #<closure (#f v)>
=== main_code (name=#f, code=0x2878340, size=4, const=0 stack=1):
signatureInfo: ((#f v))
     0 LREF0-PUSH               ; v
     1 CONSTI(0) 
     2 UVEC-REF(1)              ; (ref v 0)
     3 RET 

＊ ＊ ＊

This change allows us to write abstraction without worring that it taxes performance.

Tags: 0.9.6, Compiler, Inlining

2017/11/18

Rounding 1.15

When you round 1.15 to the nearest tenths, what do you get?

The elementary math gives 1.2. Many programming language implementations disagree, however:

$ cat tmp.c
#include <stdio.h>
int main()
{
    printf("%5.1f\n", 1.15);
    return 0;
}
$ gcc tmp.c && ./a.out
  1.1

Is it a bug? No, it's working as intended. The intention, however, is different from what people naturally expect.

＊ ＊ ＊

Decimal 1.15 can't be represented exactly with a binary floating point number; so internally, the runtime picks the closest binary floating point number to 1.15, which happens to be very slightly smaller than the actual 1.15. So, when you need to choose to round it to either 1.1 or 1.2---if you look at the actual number you have, you should say 1.1 is closer. (By the way, if you use 4.15 instead in the above example, you'll get 4.2. That's because the binary floating point number closest to 4.15 is slightly greater than that.)

You can use Gauche to check if that's really the case. The exact function tries to find the simplest rational number within the error boundary of the floating point number, but using real->rational you can get the exact number represented internally by the floating point number.

gosh> (exact 1.15)
23/20
gosh> (real->rational 1.15 0 0 #f)
2589569785738035/2251799813685248

And indeed, the exact one is smaller than the one you naturally expect from the notation:

gosh> (< 2589569785738035/2251799813685248 23/20)
#t

With 4.15, the exact one is greater than the closest simplified one:

gosh> (exact 4.15)
83/20
gosh> (real->rational 4.15 0 0 #f)
2336242306698445/562949953421312
gosh> (> 2336242306698445/562949953421312 83/20)
#t

So, if you take a point of view that a binary floating point number stands for the value it exactly represents (which is how they're treated inside the computer), you should round "the closest number to 1.15" to 1.1.

When users complain, we programmer tend to say "Floating point numbers have error. Use arbitrary precison arithmetic!" Well, floating point numbers themselves don't have error, per se. It has a precisely defined exact value, sign * mantissa * 2^exponent. It is an operation that has error, and in this case, it is the conversion from the decimal notation 1.15 to a binary floating point number.

＊ ＊ ＊

But is it the only valid interpretation?

Another view is that when we treat a value noted "1.15", it is intended to be exactly 1.15 but we take the closest floating-point number as an approximation. The distinction is subtle but important---in the previous view, the intended value is 2589569785738035/2251799813685248 in floating-point number, and 1.15 is approximation. In the current view, the intended value is 1.15, and 2589569785738035/2251799813685248 in floating-point number is the approximation.

In this view, rounding "1.15" to the nearest tenths should result "1.2". (To be precise, we must also assume round-half-up or round-half-to-even rule). This usually fits user's expectation better. But it may be costly that we have to first obtain the optimal decimal representation of the given floating point number to decide which way to round.

＊ ＊ ＊

We see both views are useful depending on circumstances. So we decided to support both.

The format procedure now supports floating-point number output directive, ~f. You can specify the field width and precision:

(format "~6,3f" 3.141592) ⇒ " 3.142"

If we need to round to the given precision, the default is to take the exact value of the floating-point number---the first view we discussed above. We call it effective rounding.

(format "~6,1f" 1.15)  ⇒ "   1.1"

However, if you need the latter view---we call it notational rounding---you can have it with : flag.

(format "~6,1:f" 1.15) ⇒ "   1.2"

Tags: 0.9.6, Flonums, format

2017/08/29

Pretty printer (and more) in REPL

It is daunting when you evaluate an expression on REPL and realize the result is a huge S-expr. Especially when you're running gosh inside Emacs with font-lock mode, since Emacs gets crawling trying to parse the huge output.

The reason I don't want to abbreviate the output was that I frequently copy the REPL output and reuse it---with Emacs, copying one S-expr is just a couple of keystrokes, no matter how big it is---but the big output dragging Emacs is irritating, nonetheless.

Gauche had several mechanisms to improve it for long time, but I finally put things together into a usable feature.

Sample session

Let me take you a little tour, for it is easier to see in examples. First, we need some interesting data.

gosh> ,u data.random
gosh> ,u gauche.generator
gosh> (define word (gmap string->symbol (strings-of (integers-poisson$ 12) (chars$ #[A-Z]))))
word
gosh> (define leaf? (samples$ '(#t #f #f #f)))
leaf?
gosh> (define (tree d) (cons (if (or (zero? d) (leaf?)) (word) (tree (- d 1)))
                             (if (or (zero? d) (leaf?)) '() (tree (- d 1)))))
tree

(tree N) would generate random nested list of max depth N. You can make several tries to find a reasonable size of the data.

gosh> (tree 5)
((HESUBSPMIBQBBWWZZ (((EHMZYLCL) QZKTHLZIKIXS)) NTAQUDHAXX (FMEBQP) PSHRSTW) ((UAYIBNNC (XAPYQBPOHSY) QFIZMITEWULRBMEO)) (WLQITJTZNBO (GJZNEKWBMLGCWKLPN) EINLIRVDLLGPQ) ((HZBDNGYBBQD)) YIQZWPL RELGWZEGSR)

Looks good, so let's save it.

gosh> (define t *1)
t

Now, all the tree in one line is hard to understand. Let's pretty-print it.

gosh> ,pm pretty #t
Current print mode:
  length :  50
   level :  10
  pretty :  #t
   width :  79
    base :  10
   radix :  #f
gosh> t
((HESUBSPMIBQBBWWZZ (((EHMZYLCL) QZKTHLZIKIXS)) NTAQUDHAXX (FMEBQP) PSHRSTW)
 ((UAYIBNNC (XAPYQBPOHSY) QFIZMITEWULRBMEO))
 (WLQITJTZNBO (GJZNEKWBMLGCWKLPN) EINLIRVDLLGPQ) ((HZBDNGYBBQD)) YIQZWPL
 RELGWZEGSR)

The ,pm toplevel command is an abbreviation of ,print-mode. Yes, setting print mode pretty to #t makes REPL pretty-prints the result.

The pretty printer tries to fit the S-expression within width. You can change it.

gosh> ,pm width 40
Current print mode:
  length :  50
   level :  10
  pretty :  #t
   width :  40
    base :  10
   radix :  #f
gosh> t
((HESUBSPMIBQBBWWZZ
  (((EHMZYLCL) QZKTHLZIKIXS)) NTAQUDHAXX
  (FMEBQP) PSHRSTW)
 ((UAYIBNNC (XAPYQBPOHSY)
   QFIZMITEWULRBMEO))
 (WLQITJTZNBO (GJZNEKWBMLGCWKLPN)
  EINLIRVDLLGPQ)
 ((HZBDNGYBBQD))
 YIQZWPL
 RELGWZEGSR)

It's still too long, so let's limit the length of the printed list:

gosh> ,pm length 3
Current print mode:
  length :   3
   level :  10
  pretty :  #t
   width :  #f
    base :  10
   radix :  #f
gosh> t
((HESUBSPMIBQBBWWZZ
  (((EHMZYLCL) QZKTHLZIKIXS)) NTAQUDHAXX
  ....)
 ((UAYIBNNC (XAPYQBPOHSY)
   QFIZMITEWULRBMEO))
 (WLQITJTZNBO (GJZNEKWBMLGCWKLPN)
  EINLIRVDLLGPQ)
 ....)

Lists (and vectors) longer than 3 elements are abbreviated using ellipses. You can also limit the number of nesting level:

gosh> ,pm level 3
Current print mode:
  length :   3
   level :   3
  pretty :  #t
   width :  40
    base :  10
   radix :  #f
gosh> t
((HESUBSPMIBQBBWWZZ (#) NTAQUDHAXX ....)
 ((UAYIBNNC # QFIZMITEWULRBMEO))
 (WLQITJTZNBO (GJZNEKWBMLGCWKLPN)
  EINLIRVDLLGPQ)
 ....)

The lists nested deeper than the current level are shown as #.

If you need to see everything, e.g. to copy & paste, you can use ,pa toplevel command (shorthand of ,print-all), which writes previous result without abbreviation.

gosh> ,pa
((HESUBSPMIBQBBWWZZ (((EHMZYLCL) QZKTHLZIKIXS)) NTAQUDHAXX (FMEBQP) PSHRSTW) ((UAYIBNNC (XAPYQBPOHSY) QFIZMITEWULRBMEO)) (WLQITJTZNBO (GJZNEKWBMLGCWKLPN) EINLIRVDLLGPQ) ((HZBDNGYBBQD)) YIQZWPL RELGWZEGSR)

You can also change the default base radix of integers by base. The radix mode switches whether radix prefix (#b, #x, #nr etc.) should be printed.

gosh> ,pm base 2
Current print mode:
  length :   3
   level :   3
  pretty :  #t
   width :  #f
    base :   2
   radix :  #f
gosh> 4753
1001010010001
gosh> ,pm base 16 radix #t
Current print mode:
  length :   3
   level :   3
  pretty :  #t
   width :  40
    base :  16
   radix :  #t
gosh> 4753
#x1291

Now, get back to the default.

gosh> ,pm default
Current print mode:
  length :  50
   level :  10
  pretty :  #f
   width :  79
    base :  10
   radix :  #f

You may notice that we have length=50 and level=10 as default. This prevents accidentally printing huge S-expression, while most useful data can be printed entirely.

Write controls

Common Lisp has several special (dynamic) variables such as *print-length* and *print-pretty* that affect how print (Scheme's write) works. Our REPL's print-mode imitates that, but instead of using individual dynamic parameters we have a packaged structure, <write-controls>. A new write-controls can be created by make-write-controls:

gosh> (make-write-controls)
#<write-controls (:length #f :level #f :base 10 :radix #f :pretty #f :width #f)>
gosh> (make-write-controls :length 10 :base 2)
#<write-controls (:length 10 :level #f :base 2 :radix #f :pretty #f :width #f)>

Write controls structure is immutable. If you want a controls that's only slightly different from existing controls, you can use write-controls-copy, to which you can give keyword arguments you want to change:

gosh> (write-controls-copy *1 :pretty #t)
#<write-controls (:length 10 :level #f :base 2 :radix #f :pretty #f :width #f)>

Gauche's output procedures such as write or display are extended to accept optional write controls.

Limitations

Currently, the pretty printer only handles lists, vectors and uniform vectors. Other objects (including objects with custom printer) are formatted by the system's default writer, so it is rendered as an unbreakable chunk. Ideally, we'd like to pretty-print such objects as well.

Pretty-printing Scheme code requires more features---it must recognize syntactic keywors and adjust indentation. Such feature will be pretty handy to format result of macro transformation, for example. We're planning to support it eventually.

Tags: 0.9.6, pretty-printing

2017/05/23

A heads-up for an incompatible fix in util.match

TL;DR: If you match records with inheritance using $ or struct match pattern, you need to change the code for 0.9.6.

We fixed a bug in the positional record matching pattern of match, existed in 0.9.5 and before. The fix actually breaks previously documented behavior, but we believe the previous behavior was incorrect and decided it's better to fix now.

Background

The $, or struct pattern allows you to extract slot values from objects using match (ref:match):

(define-class <point> ()
  ((x :init-keyword :x)
   (y :init-keyword :y)
   (z :init-keyword :z)))

(match (make <point> :x 1 :y 2 :z 3)
  [($ <point> a b c)
   (list a b c)])  => (1 2 3)

However, Gauche's object system isn't designed to access slots with their positions. You use slot names instead. In match, you can use object pattern (or @ in sort) to match with slot values, using slot names.

(match (make <point> :x 1 :y 2 :z 3)
  [(@ <point> (x a) (y b) (z c))
   (list a b c)])  => (1 2 3)

The reason we provided $ was for the compatibility of original Wright's match, which aimed at struct types provided in some Scheme impelementations. We didn't give much thought to it; just made the pattern match with the slot values of the order of class-slots (ref:class-slots). It works just fine with srfi:9 records:

(define-record-type pare (make-pare fst snd) pare?
  (fst get-fst)
  (snd get-snd))

(match (make-pare 1 2)
  [($ pare a b)
   (list a b)])  => (1 2)

Problem

Things got complicated when inheritance enters the picture. How the inherited slots are laid out depends on the implementation of metaclass (ref:compute-slots generic function), and because of multiple inheritance, the slot layout of class S doesn't necessarily a subsequence of the layout of class T that inheriting S. This is highly confusing, and we've always recommended using object match in such a case, in the manual.

However, srfi:99 records only allows single inheritance chain, and the default constructor takes initial value of inherited slot first. So it is a natural call to make positional match in the same way.

(define-record-type S make-S S?
  a b)

(define-record-type (T S) make-T T?   ;; inherit S
  c d)

(make-S 1 2)      ;; Initialize a=1, b=2

(make-T 1 2 3 4)  ;; Initialize a=1, b=2, c=3, d=4

;; Then, ($ T w x y z) should match with w=1, x=2, y=3, z=4.

It hadn't been so. The compute-slots method of <record> placed the direct slots first, followed by the inherited slots. It needs to do so to be consistent with that "fields in derived record types shadow fields of the same name in a parent record type", as defined in srfi-99.

Thus, ($ T w x y z) pattern in the above example matched w=3, x=4, y=1, and z=2. This wasn't inconsistent with the manual, which stated that positional match was done with the order of class-slots. It was an unintended artifact of implementation that was overlooked, unfortunately.

It also had a defect when duplicate slot names existed. When a subclass defines a slot with the same name as inherited slot, the standard compute-slots merges them into one, which is also CLOS's behaviro. However, srfi:99 record types allow subtype to have slots with the same name but as independent slots.

(define-record-type S #t #t
  a)

(define-record-type (T S) #t #t
  a)

(define t (make-T 1 2))

(T-a t)  ;=> 2    ; accesses T's a
(S-a t)  ;=> 1    ; accesses S's a in T

(slot-ref t 'a) ;=> 2  ; named access takes the subtype's slot

The existing implementation of positional matching needed to rely on named slot access, and didn't work on such record types.

Fix

We introduced a generic function to be specialized with metaclass, that handles positional access within match. We keep the underlying mechanism undocumented for now; changing the way of positional matching should be rare and based on well-established customs. The order of record types fits this criteria, and made to work as expected:

(define-record-type S make-S S?
  a b)

(define-record-type (T S) make-T T?   ;; inherit S
  c d)

(match (make-T 1 2 3 4)
  [($ T w x y z) (list w x y z)]) => (1 2 3 4)

Now it also works with record types having duplicate slot names:

(define-record-type S #t #t
  a)

(define-record-type (T S) #t #t
  a)

(match (make-T 1 2)
  [($ T x y) (list x y)])   ;=> (1 2);  was (2 2) before

We hope few have used positional match with inherited records--- the old behavior seems apparently wrong---so we decided to fix this now.

If you happen to have the code that relies on the previous behavior, and need to make it work with both versions, you can switch to use named match (object or @).

Tags: 0.9.6, util.match, gauche.record