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:
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:
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]
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.
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.
If you intend to do a fair amount of travelling and your stay is <3 weeks, it may be worth getting a JR Pass[1]. It doesn't work for all lines, but does include the Shinkansen and several of the major inner-city lines. Buses too.
Probably not worth it if you're only visiting one city as the pass is quite expensive. There are regional tourist passes though.
Unfortunately the 70% price rise on the JR pass back in 2023 made it much less likely to be economic for most people compared to just buying tickets as you go, even for trips that visit more than one city. Last time I was there I did a loop up from Tokyo to Hokkaido and back by rail, and it was still cheaper to buy individual tickets. (There are obviously still some itineraries where it works out cheaper, but it's much less of an "obviously good idea for most people" than it was back before 2023.)
Having followed some tourists coming to Japan, a large amount of the people appreciate convenience, and the rail pass gives them that. The price is secondary.
Hell, there are even people paying the equivalent of 100 USD just to have someone pick them up from the Haneda airport and accompany them to the hotel. Not even a taxi service, just to be with them to buy them the train tickets, etc.
The silly thing is that your "blockchain" could be the smartest thing in the world, have super incredible cryptography or whatever. You can have the smartest developers in the world writing the software without bugs.
But you run that software on a mainstream operating system (Linux/Windows), your funds are not safu - they're just one confused deputy away from being stolen.
Having a secure by design operating system is a fundamental requirement for "blockchain" to ever become more than an online casino.
Online payments through centralized entities don't have this problem. If you get hacked, someone can revert the payment. If you get hacked and the private keys for your smart contract are stolen, there's nobody who can just roll it back for you.
The OS is the weakest link - a side-channel that will bypass any and all clever cryptocurrency designs.
That should have been true, but unfortunately the most popular programming languages do not have distinct data types for bit strings, non-negative numbers, integer residues a.k.a. modular numbers, binary polynomials and binary polynomial residues.
So in C and the like one uses "unsigned" regardless if bit strings or non-negative numbers are needed.
Because no explicit conversions between bit strings and numeric types are used, it is frequent to have expressions where a certain endianness of the numbers is assumed implicitly.
This is the most frequent source of bugs that manifest when a program is run on a machine with an opposite endianness than assumed in the program.
This. In the specific case of endianness, if you have bugs with it you're probably already doing something wrong. But in general, supporting weird architectures is not something that should be expected to be foisted on any arbitrary projects, especially if the person who does the initial port just disappears again.
S-expressions are more like the tupled argument form, but better.
(f x y z)
Is equivalent to:
(f . (x . (y . (z . ())))
Every function takes one argument - a list.
Lists make partial application simpler than with tuples (at least Haskell style tuples), because we don't need to define a new form for each N-sized tuple. Eg, in Haskell you'd need:
partial2 : (((a, b) -> z), a) -> (b -> z)
partial3 : (((a, b, c) -> z), a) -> ((b, c) -> z)
partial4 : (((a, b, c, d) -> z), a) -> ((b, c, d) -> z)
...
With S-expressions, we can just define a partial application which takes the first argument (the car of the original parameter list) and returns a new function taking a variadic number of arguments (the cdr of the original parameter list). Eg, using a Kernel operative:
($define! $partial
($vau (f first) env
($lambda rest
(eval (list* f first rest) env))))
($define! f ($lambda (x y z) (+ x y z)))
(f 3 2 1)
=> 6
($define! g ($partial f 3))
(g 2 1)
=> 6
($define! h ($partial g 2))
(h 1)
=> 6
($define! i ($partial h 1))
(i)
=> 6
We could perhaps achieve the equivalent in Haskell explicitly with a multi-parameter typeclass and a functional dependency. Something like:
class Partial full first rest | full first -> rest where
partial :: (full -> z, first) -> (rest -> z)
instance Partial ((a,b)) a b where
partial (f, a) = \b -> f (a, b)
instance Partial ((a, b, c)) a ((b, c)) where
partial (f, a) = \(b, c) -> f (a, b, c)
instance Partial ((a, b, c, d)) a ((b, c, d)) where
partial (f, a) = \(b, c, d) -> f (a, b, c, d)
...
That's one way to look at it, but the major difference is that one can also pass a a list as one argument, as in `(f x y z)` and `(f (list x y z)` are not the same. The thing with tuples is that a tuple of one datum is the very same as that datum itself and the same is true with the currying situation. `(f x) y` and `f x y` are truly one and the same in Haskell and Ocaml, just as `f(x, y)` and `let val a = (x,y) in f x` are one and the same in SML. This is not the case in Rust where `f(x,y)`, a function called with two arguments, and `f((x,y))`, a function called with one argument that is a tuple of two arguments are two different things.
There is also a difference in Scheme between returning a single value that is a list containing multiple values, and actually returning multiple values, In Rust however there is no difference between returning two values and returning a pair of two values. So Rust functions actually do properly take multiple arguments but always return a single one which may or may not be a tuple. In SML, Haskell and OCaml all functions technically take only one argument and return one value.
(Properly formatted) XML can be parsed, and streamed, by a visibly-pushdown automaton[1][2].
"Visibly Pushdown Expressions"[3] can simplify parsing with a terse syntax styled after regular expressions, and there's an extension to SQL which can query XML documents using VPAs[4].
JSON can also be parsed and validated with visibly pushdown automata. There's an interesting project[5] which aims to automatically produce a VPA from a JSON-schema to validate documents.
In theory these should be able outperform parsers based on deterministic pushdown automata (ie, (LA)LR parsers), but they're less widely used and understood, as they're much newer than the conventional parsing techniques and absent from the popular literature (Dragon Book, EAC etc).
I'm not an academic and have extensive experience with parsing.
But for whataver reason, VPAs have slipped under my radar until very recently - I only discovered them a few weeks ago and have been quite fascinated. Have been reading a lot (the citations I've given are some of my recent reading), and am currently working on a visibly pushdown parser generator. I'm more interested in the practical use than the acamedic side, but there's little resources besides academic papers for me to go off.
Thought it might be interesting to share in case others like me have missed out on VPAs.
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.
There's some syntax sugar for right chains of pairs to form lists: ---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 `()`.
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: And now we can define the `eml` function as an alias for `cons`. 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: 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:
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:
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
reply