HackerTrans
TopNewTrendsCommentsPastAskShowJobs

sparkie

no profile record

comments

sparkie
·28 วันที่ผ่านมา·discuss
That may be true, but it may also mean you utilize more memory than you need to. If you aren't shrinking the array when you no longer need previously allocated capacity then you're wasting memory. You could end up with an array of 10 elements and an allocation of 2^10.

The capacity as bit_ceil(len) ensures that at most, half of the allocated space is wasted - excess space is O(n).
sparkie
·28 วันที่ผ่านมา·discuss
I don't think it's that rare. I've been using the technique for years, and I've seen it done in other work. Bagwell's VList[1] for example uses the equivalent of `bit_ceil` to determine the size of each block without having to store it - and there are earlier works based on the same trick. RAOTS, which is referenced by the VList, mentions using the technique, but itself uses a slightly more complex trick where we can calculate the size of a block based on the approx square root of the length.

You can use the trick if the array can shrink as long as you always shrink the allocation when length goes below the next power of 2 not greater than len (which may make use of stdc_bit_floor).

[1]:https://cl-pdx.com/static/techlists.pdf
sparkie
·28 วันที่ผ่านมา·discuss
If you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.
sparkie
·28 วันที่ผ่านมา·discuss
In C23 this approach is nice, but in older versions of C we end up with awful macros where we need to define the structure before we use it.

    #define Array(T) struct array_##T
    #define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
    
    DEFINE_ARRAY(int);
    Array(int) foo;
    Array(int) bar;
C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front.

    #define Array(T) struct array_##T { size_t len; T *elems; }

    Array(int) foo;
    Array(int) bar;
sparkie
·28 วันที่ผ่านมา·discuss
The reason the struct is avoided here is so the array can be typed to its element type (rather than casting to and from `void*`).

With a struct we would need one struct for each element type - at least prior to C23 which provides a better approach where we can declare the same struct multiple times in a translation unit.

    #define Array(T) struct array_##T { size_t len; T *elems; }
We can use `Array(int)` in multiple places in the same TU - but in C11 or earlier, this is an error.
sparkie
·28 วันที่ผ่านมา·discuss
The concept of not storing capacity isn't silly. If you need to reserve space then it's not the appropriate structure, but it's otherwise fine.

However, using an 2-element array to avoid using a struct is silly.
sparkie
·28 วันที่ผ่านมา·discuss
Really? It's been done plenty and I thought was quite common knowledge. Some of the <stdbit.h> provided functions are basically for this purpose.

stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction.

stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1).

The approach isn't used in older (90s and earlier) texts because hardware support for popcount/clz wasn't commonplace and the cost to do it in software wasn't worth it, but it is mentioned in some texts.
sparkie
·เดือนที่แล้ว·discuss
Bitcoin has a variable width encoding (`CompactSize`), but it doesn't prevent overlong encodings - however there are various canonicalization rules in the Bitcoin protocol to require minimal encoding.
sparkie
·2 เดือนที่ผ่านมา·discuss
The C charter has a rule of "no invention".

Anything needs to be demonstrated and used in practice before being included in the standard. The standard is only meant to codify existing practices, not introduce new ideas.

It's up to compiler developers to ship first, standardize later.
sparkie
·2 เดือนที่ผ่านมา·discuss
Lisps are expression based languages, but not pure. It's easy to mistake it as "like most other languages", but it's not quite the same - everything is an expression and returns a result. There are no "statements".

They appear procedural because of syntax sugar - ie, the body of a function is basically implicitly wrapped in (progn ...), (begin ...), ($sequence ...), etc - which are all equivalent expression forms which evaluate their sub-expressions in order and return the result of the last one.

   (progn a b c)      ;; CommonLisp
   (begin a b c)      ;; Scheme
   ($sequence a b c)  ;; Kernel

   ;; evaluate a, then b, then c, 
   ;; ignore the results of evaluating a and b 
   ;; return the result of evaluating c.
So when you see:

   (define (foo)
       (expr1)
       (expr2)
       (expr3))
If we desugar, it would be

    (define foo (lambda () (begin (expr1) (expr3) (expr3))))
We get behavior that looks just like other procedural languages (without a "return" keyword) - but everything is still an expression.

A similarity is the comma operator in C. Imagine you didn't write statements but the body of your C functions was entirely chains of comma operators.

CommonLisp has a couple of other useful related forms - prog1 and prog2. They still evaluate their sub-expressions in order, but prog1 returns the result of evaluating the first expression, and prog2 returns the result of the second expression.

    (define (foo) (prog1 (expr1) (expr2) (expr3))
    (foo)
 
    ;; evaluates expr1, then expr2, then expr3
    ;; returns the result of evaluating expr1
    ;; ignores the results of evaluating expr2 and expr3
sparkie
·2 เดือนที่ผ่านมา·discuss
Operatives are based on FEXPRS from older lisps - they're basically a function-like form, but where the operands are not implicitly reduce at the time of call.

    (foo (+ 2 3) (* 3 4))
    ($bar (+ 2 3) (* 3 4))
`foo` is a function, when it is combined with the arguments, it receives the values 5 and 7.

`$bar` however, receives its operands verbatim. It receives (+ 2 3) as its first operand and (* 3 4) as its second - unevaluated.

The operative/FEXPR body decides how to evaluate the operands - if at all.

The difference between an operative/FEXPR and a macro is that macros are second-class objects which must appear in their own name - we cannot assign them to variables, pass them or return them from functions. Operatives and FEXPRs are first-class objects that can be treated like any other.

The difference between FEXPRs and Operatives is to do with scoping and environments. FEXPRs were around before Scheme - when Lisps were dynamically scoped. This meant we could have unpredictable behavior and so called "spooky action at distance". They were problematic and basically abandoned almost entirely in the 1980s.

Shutt introduced Operatives as a more hygienic version - based on statically scoped Scheme. Instead of the operative being able to mutate the dynamic environment arbitrarily, there are limitations. The first part of this is that environments are made into first-class objects - so we can assign them to a symbol and pass them around. The final part is that an operative receives a reference to the dynamic environment of its caller - which we bind to a symbol using the operative constructor, `$vau`.

    ($vau (operands) dynamic-env . body)
Compare to:

    ($lambda (arguments) . body)
So operatives are called in the same way a function is called - but the operands are not reduced, and the environment is passed implicitly.

The body can decide to evaluate the operands using the environment of the caller - essentially behaving as if the caller had evaluated them

    (eval operands dynamic-env)

But it can chose other evaluation strategies for the operands - such as evaluating them in a custom created environment which we can make with (make-environment) or ($bindings->environment).

This also allows the operative to mutate the environment of its callee - but only the locals of that environment. The parent environments cannot be mutated through the reference `dynamic-env`.

Technically, `$lambda` is not primitive in Kernel - though it is the main constructor of applicatives (functions) - the primitive constructor is called `wrap` - and it takes another combiner (an operative or applicative) as its parameter. Wrapping a combiner simply forces the evaluation of its arguments when called - so functions are just wrappers around operatives - and the underlying operative of any function can be extracted with `unwrap`.

There's a lot more to them. They're conceptually quite simple in terms of implementation, but they have enormous potential use cases that are unexplored.

Read more on the Kernel page[1]. In particular, the Kernel report[2]. There's also a formal calculus describing them, called the vau calculus[3].

[1]:https://web.cs.wpi.edu/~jshutt/kernel.html

[2]:https://ftp.cs.wpi.edu/pub/techreports/pdf/05-07.pdf

[3]:https://web.archive.org/web/20150224035948/http://www.wpi.ed...
sparkie
·2 เดือนที่ผ่านมา·discuss
There's no "external representation" for environments. In klisp it will just print:

    [#environment]
The environment type is encapsulated, so it doesn't give you very useful debug information.

Perhaps having `@` produce an environment is the wrong approach and we should just produce an association list instead - then move `$bindings->environment` into the `?` operative to enable querying.
sparkie
·2 เดือนที่ผ่านมา·discuss
I use klisp[1] and bronze-age-lisp[2] mostly for testing, as they're the closest to a feature complete implementation of the Kernel Report.

I've written a number of less complete interpreters over the years. I currently have a long-running side-project to provide a more complete, highly optimized implementation for x86_64.

[1]:https://github.com/dbohdan/klisp

[2]:https://github.com/ghosthamlet/bronze-age-lisp
sparkie
·2 เดือนที่ผ่านมา·discuss
I understand the use case, but Scheme macros never felt intuitive to me. I think it may be the quotation more than anything that I dislike - though I also dislike that they're second class (which was the key thing which led me to Kernel).

I use C preprocessor macros extensively and don't have the typical dislike for them that many people have - though I clearly understand their limitations and the advantage Scheme macros have over them.

Since learning Kernel, the boundary of "compile time" and "runtime" is more blurry - I can write operatives which behave somewhat like a macro, and I do more "multi-stage" programming, where one operative optimizes its argument to produce something more efficient which is later evaluated - though there are still limitations due to the inability to fully compile Kernel.

As one example, I've used a kind of operative I call a "template", which evaluates its free symbols ahead of time but doesn't actually evaluate the body. When we later apply the some operands it replaces the bound symbols with the operands, looking up any symbols to produce an expression which we don't need to immediately evaluate either - but this expression has all symbols fully resolved. This is somewhere between a macro and regular operative.

Consider:

    ($define! z 10)

    ($define! @add-z
        ($template (x y)
            (+ x y z)))
In this template `x` and `y` are bound variables and `+` and `z` are free. The template resolves the free symbols and returns an operative expecting 2 operands, effectively providing an operative with the body:

    ([#applicative: +] x y 10)
When we call the template with the two operands, it resolves any symbols in the arguments and returns the full expression with no symbols present, but it doesn't evaluate the expression yet.

    > ($let ((x 9)
             (y 7))
          (@add-z (* x 3) (- y 13)))
    ([#applicative: +] ([#applicative: *] 9 3) ([#applicative: -] 7 13) 10)
When we decide to evaluate the expression, no symbol lookup is necessary - it can perform the operation rather quickly, despite the slow interpretation.

---

The $template form above isn't too difficult to implement. I've iterated several forms of this - some which only partially resolved the bound symbols, but lost them in a RAID failure. An earlier version which has some issues I still have because I put it online:

    ($provide! ($template)
        ($define! $resolve-free-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-free-symbols) 
                                     (list params (car expr)) 
                                     env)
                              (apply (wrap $resolve-free-symbols) 
                                     (list params (cdr expr)) 
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             expr
                             (eval expr env)))
                    (#t expr))))

        ($define! $resolve-bound-symbols
            ($vau (params expr) env
                ($cond
                    ((null? expr) ())
                    ((pair? expr)
                        (cons (apply (wrap $resolve-bound-symbols)
                                     (list params (car expr))
                                     env)
                              (apply (wrap $resolve-bound-symbols)
                                     (list params (cdr expr))
                                     env)))
                    ((symbol? expr)
                        ($if (member? expr params)
                             (eval expr env)
                             expr))
                    (#t expr))))

        ($define! zip
            ($lambda (fst snd)
                ($cond
                    (($and? (null? fst) (null? snd)) ())
                    (($and? (pair? fst) (pair? snd))
                        (cons (list (car fst)
                                    (list* (($vau #ignore #ignore list)) (car snd)))
                              (zip (cdr fst) (cdr snd)))))))

        ($define! $template
            ($vau (params body) senv
                ($let ((newbody 
                        (eval (list $resolve-free-symbols params body) senv)))
                    ($vau args denv
                        (eval (list $resolve-bound-symbols params newbody)
                              (eval (list* $bindings->environment
                                           (zip params args))
                                    denv))))))) 

---

At present the best interpreter is klisp, and the fastest is bronze-age-lisp, which uses klisp - with parts of hand-written 32-bit x86 assembly.

I've been working on a faster interpreter for a number of years as a side project, optimized for x86_64 with some parts C and some parts assembly. It has diverged in some parts from the Kernel report, but still retains what I see are the key ingredients.

My modified Kernel has optional types, and we have operatives to `$typecheck` complex expressions ahead of evaluating them. I intend to go all in on the "multi-stage" aspect and have operatives to JIT-compile expressions in a manner similar to the above template.
sparkie
·2 เดือนที่ผ่านมา·discuss
Operatives do that for me, better than macros. Parent is correct that macros are compile time, which gives them a performance advantage over operatives - but IMO, they're not better ergonomically. I find operatives simpler, cleaner and more powerful.
sparkie
·2 เดือนที่ผ่านมา·discuss
In Kernel I would use something like this:

    true        #t
    false       #f
    null        ()
    [...]       (& ...)
    "k" : v     (: k v)
    {...}       (@ ...)  
Where &, :, @ are defined as:

    ($define! &
        ($lambda args (cons list args)))

    ($define! : 
        ($vau (key value) env
            (list key (eval value env))))
            
    ($define! @ 
        (wrap 
            ($vau kvpairs env 
                (eval (list* $bindings->environment kvpairs) env))))
Using the "person" example from the JSON/syntax section on Wikipedia:

    ($define! person
        (@
            (: first_name "John")
            (: last_name "Smith")
            (: is_alive #t)
            (: age 27)
            (: address 
                (@
                    (: street_address "21 2nd Street")
                    (: city "New York")
                    (: state "NY")
                    (: postal_code "10021-3100")))
            (: phone_numbers
                (& (@ (: type "home") (: number "212 555-1234"))
                   (@ (: type "office") (: number "646 555-4567"))))
            (: children
                (& "Catherine" "Thomas" "Trevor"))
            (: spouse ())))
I would then define `?`

    ($define! ? $remote-eval)
Now we can query the object.

    > (? age person)
    27

    > (? postal_code (? address person))
    "10021-3100"

    > (car (? children person))
    "Catherine"

    > (cdr (? children person))
    ("Thomas" "Trevor")

    > (? type (cadr (? phone_numbers person)))
    "office"

    > (? number (car (? phone_numbers person)))
    "212 555-1234"

    > ($define! full_name ($lambda (p) (string-append (? first_name p) " " (? last_name p))))
    > (full_name person)
    "John Smith"
sparkie
·2 เดือนที่ผ่านมา·discuss
When I learned Scheme, I liked the language but strongly disliked macros and quotation. I'd only been using it a short while and when I searched for solutions to a few problems these "fexpr" things kept appearing up, which i didn't understand, and this "Kernel" language. I decided to learn it since "fexprs" were apparently the solution to several of my problems. This wasn't easy at first - I had to read the Kernel Report several times, but I ended up finding it way more intuitive than using macros and quotes.

I've not written a Scheme macro since. I've written hundreds of Kernel operatives though.

I was also a typoholic previously, but am in remission now thanks to Kernel.

https://web.cs.wpi.edu/~jshutt/kernel.html
sparkie
·3 เดือนที่ผ่านมา·discuss
It's potentially useful for computer algebra with complex numbers - we might be able to simplify formulas using non-standard methods, but instead via pattern matching. We might use this to represent exact numbers internally, and only produce an inexact result when we later reduce the expression.

Consider it a bit like a "church encoding" for complex numbers. I'll try to demonstrate with an S-expression representation.

---

A small primer if you're not familiar. S-expressions are basically atoms (symbols/numbers etc), pairs, or null.

    S = <symbol>
      | <number>
      | (S . S)      ;; aka pair
      | ()           ;; aka null
    
There's some syntax sugar for right chains of pairs to form lists:

    (a b c)          == (a . (b . (c . ()))   ;; a proper list
    (a b . c)        == (a . (b . c))         ;; an improper list
    (#0=(a b c) #0#) == ((a b c) (a b c))     ;; a list with a repeated sublist using a reference
---

So, we have a function `eml(x, y) and a constant `1`. `x` and `y` are symbols.

Lets say we're going to replace `eml` with an infix operator `.`, and replace the unit 1 with `()`.

    C = <symbol>
      | <number>
      | (C . C)      ;; eml
      | ()           ;; 1
We have basically the same context-free structure - we can encode complex numbers as lists. Let's define ourselves a couple of symbols for use in the examples:

    ($define x (string->symbol "x"))
    ($define y (string->symbol "y"))
And now we can define the `eml` function as an alias for `cons`.

    ($define! eml cons)

    (eml x y)
    ;; Output: (x . y)
We can now write a bunch of functions which construct trees, representing the operations they perform. We use only `eml` or previously defined functions to construct each tree:

    ;; e^x

        ($define! exp     ($lambda (x) (eml x ())))
        
        (exp x)
        ;; Output: (x)
        ;; Note: (x) is syntax sugar for (x . ())

    ;; Euler's number `e`

        ($define! c:e     (exp ()))
        
        c:e          
        ;; Output: (())
        ;; Note: (()) is syntax sugar for (() . ())

    ;; exp(1) - ln(x)

        ($define! e1ml    ($lambda (x) (eml () x)))
        
        (e1ml x) 
        ;; Output: (() . x)

    ;; ln(x)

        ($define! ln      ($lambda (x) (e1ml (exp (e1ml x)))))
        
        (ln x)
        ;; Output: (() (() . x))

    ;; Zero

        ($define! c:0      (ln ()))
        
        c:0
        ;; Output: (() (()))

    ;; -infinity

        ($define! c:-inf   (ln 0))
        
        c:-inf
        ;; Output: (() (() () (())))

    ;; -x
        
        ($define! neg      ($lambda (x) (eml c:-inf (exp x))))

        (neg x)
        ;; Output: ((() (() () (()))) x)
        
    ;; +infinity
    
        ($define! c:+inf   (neg c:-inf))
        
        c:+inf
        ;; Output: (#0=(() (() () (()))) #0#)
        
    ;; 1/x
    
        ($define! recip    ($lambda (x) (exp (eml c:-inf x))))
        
        (recip x)
        ;; Output: (((() (() () (()))) . x))
  
    ;; x - y
    
        ($define! sub      ($lambda (x y) (eml (ln x) (exp y))))
    
        (sub x y)
        ;; Output: ((() (() . x)) y)
    
    ;; x + y
    
        ($define! add      ($lambda (x y) (sub x (neg y))))
    
        (add x y)
        ;; Output: ((() (() . x)) ((() (() () (()))) y))
    
    ;; x * y
    
        ($define! mul      ($lambda (x y) (exp (add (ln x) (exp (neg y))))))
        
        (mul x y)
        ;; Output: (((() (() () (() . x))) (#0=(() (() () (()))) ((#0# y)))))
        
    ;; x / y
    
        ($define! div      ($lambda (x y) (exp (sub (ln x) (ln y)))))
        
        (div x y)
        ;; Output: (((() (() () (() . x))) (() (() . y))))
        
    ;; x^y
    
        ($define! pow      ($lambda (x y) (exp (mul x (ln y)))))
  
        (pow x y)
        ;; Output: ((((() (() () (() . x))) (#0=(() (() () (()))) ((#0# (() (() . y))))))))
  
I'll stop there, but we continue for implementing all the trig, pi, etc using the same approach.

So basically, we have a way of constructing trees based on `eml`

Next, we pattern match. For example, to pattern match over addition, extract the `x` and `y` values, we can use:

    ($define! perform-addition
        ($lambda (add-expr)
            ($let ((((() (() . x)) ((() (() () (()))) y)) add-expr))
                (+ x y))))  

    ;; Note, + is provided by the language to perform addition of complex numbers

    (perform-addition (add 256 512))
    ;; Output: 768
So we didn't need to actually compute any `exp(x)` or `ln(y)` to perform this addition - we just needed to pattern match over the tree, which in this case the language does for us via deconstructing `$let`.

We can simplify the defintion of perform-addition by expanding the parameters of a call to `add` as the arguments to the function:

    ($define! $let-lambda
        ($vau (expr . body) env
            ($let ((params (eval expr env)))
                (wrap (eval (list* $vau (list params) #ignore body) env)))))
                
    ($define! perform-addition
        ($let-lambda (add x y)
            (+ x y)))

    ($define! perform-subtraction
        ($let-lambda (sub x y)
            (- x y)))


    ($define! sub-expr (sub 256 512))
    ;; Output: #inert
    sub-expr
    ;; Output: ((() (() . 256)) 512)

    (perform-subtraction sub-expr)
    ;; Output: -256

There's a bit more work involved for a full pattern matcher which will take some arbitrary `expr` and perform the relevant computation. I'm still working on that.

Examples are in the Kernel programming language, tested using klisp[1]

[1]:https://github.com/dbohdan/klisp
sparkie
·3 เดือนที่ผ่านมา·discuss
The difference is that 90s games had novelty at the time - many introduced new gameplay ideas.

A lot of today's AAA games have converged into a small number of genres like the open world action RPG games which all have the same "side quests" repeated ad-nauseam.

* Talk to NPC

* Go kill 5 monsters

* Talk to another NPC

* Collect 3 of some item.

* Talk to another (or original) NPC.

* Get some pocket change, EXP and an item as reward.

Repeated several hundred times throughout the game with minor variations and some uninteresting dialogue that doesn't develop your the story or character besides unlocking a new skill. Every skill is acquired the same way - through "skill points" that are acquired with EXP - but there's no novelty in acquiring EXP - just the same quests which increase the game's "content".

But this content is boring an uninspired. It's almost like it's done to keep people employed - or at least, to pay fewer programmer's high salaries and replace them with lower salaries of employees who can use a pre-packaged scripting system to increase the gameplay duration without adding any new gameplay. Or maybe it's the sunk cost fallacy - they feel like they've put some time and effort into implementing some mechanic, so it would be a waste to only use it once or twice, so they have to use it 50 times to justify the budget spent on developing it.
sparkie
·3 เดือนที่ผ่านมา·discuss
The subway system in Kyoto (Karasuma line) is operated by the local government. I visited during the busiest time of the year (Gion matsuri), and the trains were not overcrowded, were frequent and arrived on the dot. The subway system is nicely air conditioned which was pleasant as I visited during a heatwave.

I'm mostly in favor of privatization, but this is an example where the local government provide an exceptional service which is in no way inferior to the privately operated ones.