DEV Community: Marco Servetto

I'm releasing on youtube my Java parallelism course.

Marco Servetto — Sun, 06 Mar 2022 06:27:52 +0000

I'm releasing on youtube my Java parallelism course, NWEN303 for VUW ECS new zealand. Feel free to learn all you can from it. It is going to be fun!

Here all the lectures out up to now:

Lecture 1, with the playlist:
https://www.youtube.com/watch?v=nMgXz1iucac&list=PLWsQqjANQic-Hh5w2srBkQro0K0xMvCg0

Lecture 2
https://www.youtube.com/watch?v=uUkd0Xuk1jE
https://www.youtube.com/watch?v=GhWL0W2xWwo

Lecture 3
https://www.youtube.com/watch?v=Kgw3aveClTE
https://www.youtube.com/watch?v=07JZj32QD6w

Lecture 4
https://www.youtube.com/watch?v=SA_6Jloh2bA

How to use Java from Forty2

Marco Servetto — Sun, 13 Feb 2022 23:09:38 +0000

With code examples!
(https://www.youtube.com/watch?v=asXPD879RZo)

Freedom is slavery

Marco Servetto — Mon, 07 Feb 2022 04:17:57 +0000

There is a fascinating motto in the PL design community:

Freedom is slavery.

I think this motto is not popular enough. In this post, I will try to explain it more, hopefully you can learn about it and disseminate it too.

It is highly connected with the concept of offensive programming: you code should monitor its execution and throw error as soon as anything go out of the predicted path; hopefully with a good error message explaining what is going wrong.

Offensive programming is fundamental when working on a large project. Consider the following 3 scenarios:

One programmer for a few days with no planned maintenance; usually the customer is the single programmer.
A single team/company for a few months. We have an actual maintenance plan. Usually the customer is a wealthy individual or a small company.
A community effort for many years. In this context, maintaining is developing. For example, is 'Gimp' actively maintained or actively developed? In those cases, usually there is no clear 'customer', but a large user base.

Programming at scale

Small scale: programming is mostly to express behavior. Here offensive programming seams to be just a waste of time.
Larger scale: programming is mostly to restrict behavior. Here offensive programming really pays off: code you wrote long ago, or written by another programmer is actively teaching users how to use it by checking how it gets used. Sure, there may also be documentation.. but no one actually ever read it. Offensive programming is like a form of active documentation.

Programming is a competitive effort, a battle!

Consider a multiplayer shooter or similar game. Today, they just released a new update: yet another kind of weapon.

Attack: cool, now I can do yet another thing; more freedom, more expressive power! – Still, I can only keep up to 4 weapons in my inventory
Defense: Oh, no, now the enemy can kill me in yet another way – There are many enemies and they may have any weapon at all. How to defend against all possible weapons?

Consider a programming language. There is a new update: yet another kind of statement/expression/features/language-primitive.

Initial development: cool, now I can do yet another thing; more freedom, more expressive power! – Still, I can keep a few features in my head at once (finite brain).
Maintenance/Usability: Oh, no, now the users/coworkers can interact with my code in yet another way. – Given enough time, all possible ways to interact with my code become relevant. How to make sure my code is correct in all those scenarios?

Two kinds of gameplay: Cooperative and PvP

Continuing on the video-game metaphors, we can imagine two kinds of Programming environment:

Cooperative: This kind of programming environment is what is commonly associated to Python or Ruby: a user of you code can always break/dismantle absolutely everything if they want, and the only documentation giving FULL information on what would happen if they start playing editing the stack trace variable values or monkey patching methods is the actual source code. This gives the user full freedom, and gives the library writer full slavery. They basically can not truly guarantee anything. That may not be too bad for small projects, we can rely on conventions and cooperation, and hope for the best. Minecraft it is great for cooperative gaming, many builders can come together and build amazing things. In Minecraft it is easier to not step on each other feet that while programming: usually if my wall is not very stable, your house will not collapse. Still, cooperative Mincraft servers usually have a reasonable small number of players. The more the players, the more the risk of a griefer getting in.

This is the same for coding. If you project is big enough, or if breaking your project is worth enough money you may not be able to get enough truly trusted programmers to work on it.
Also.. do you know about supply chains attack? when hacker manages to inject adversarial code in your project by cooperating to some of the open source libraries you use.

PvP: I assume you are now opening you eyes very wide.. what a PvP programming environment can possibly look like? PvP Mincraft servers are basically giant wastelands. How can PvP programming end up any better?

The C model delusion

There is a big lie in programming: The lie is that
'Ultimately everything is broken', thus the best we can do is to just be sensible, practical and try to cooperate.

Indeed, in the old C/Shell/Lowlevel-OS programming mindset, this is correct. Many languages are just a nice way to generate arbitrary assembler, thus in the end, everything can happen.

Thankfully we are slowly moving away from it. In Java and C#, a bunch of things are actually guaranteed by the language,
that is why Java has 'security bugs/fix': because they have a security model, some properties that they promise.
In a C/C++ compiler there is no such thing as a security fix, not because C is more secure, but because there is nothing actually promised by the language.

Freedom is Slavery

In a language like Java/C#, freedom is slavery: any extra feature could potentially break some property that we had before. In Java it is actually possible to write good Offensive code that is actually guaranteed to work modularly: no matter how adversarial the user context is, your code will still be able to preserve internal constraints and to monitor its behavior against abuse. (Yes, I know, this is technically false, keep reading)

In my language, I try to get much further then Java: In Java you can still break the JVM by loading broken C code, or (on some OS) by writing on virtual files that modify your actual memory.

So... in some sense, if arbitrary adversarial code can get into your system, if we are in a real PvP scenario... you are still in the desolate wasteland.

In 42, this is not the case, and even with adversarial code injected into your security critical process, you can still build a secure fort, and ensure arbitrary representation invariants. From those, you can build a strong and flexible security system where valid objects are guaranteed to only do valid actions, and objects of those objects are the one ones able to do those kinds of actions (object capabilities).
If you are interested in the idea, please try 42 and contact me for more infos!

HashMaps and HashSets in a language with normalization

Marco Servetto — Mon, 31 Jan 2022 09:19:55 +0000

In this video I explain how in a language with normalization (also known as hashconsing) Maps and Sets are much better/faster.

https://www.youtube.com/watch?v=Rv1lsKHIQu8

The idea is that you can simply avoid arbitrarily long equality tests.
An object is normalized if it is deeply immutable and we are guaranteed that there is no other structurally equivalent immutable object in memory. Thus all the pointers to something with that structure are pointing to the same object in memory.
If an hashmap/hashset has only normalized keys, we can just check for pointer equality instead of checking the 'equals'.

Security and Correctness: two different concepts.

Marco Servetto — Thu, 27 Jan 2022 02:50:20 +0000

A few years ago I started researching on Software correctness. I was actually interested in software security, but I was unaware of the difference at the time. Now, after researching in both areas I can finally discuss the difference between those two concepts.
What does it take to mathematically define if a specific program is correct and/or secure?

Fist I will talk about correctness, then security.

We say that a program is correct if it respects its specification.
Thus, it does not even make sense to talk about the correctness of a program on its own. Correctness is actually a consistency property of a pair program + specification.

Let's consider a very simple program with a simple specification:

    //Post: the result is a positive number
    int foo(){return 5;}

Is this code correct? That is, is it true that the result of calling that method will always respect the specified post-condition?

Well... NO. For no real architecture that method will always return a positive number. In some situations calling that method will simply raise a StackOverflow error, and sometime the physical hardware will crash and burn before being able to compute the result.
However, most developers would agree that the code above is correct, or at least, as correct as it can possibly be.
That is, we are not considering correctness in an absolute sense, we are considering a simplified execution model with certain simplifications with respect to the hash reality, where anything can fail at any point anyway.

Many researchers in the area of software verification seams to simply accepting that there is going to be this set of simplifications that hopefully will be irrelevant in most real life situations an focus on mathematically modelling code execution in order to prove correctness (that is, consistency between code and specification) on such a simplified execution model.
Instead, I decided to study and categorize those simplifications:
If we can not make proofs on the actual execution model, what execution model should we use?
I say that an execution model more close to reality has a bigger scope that an execution model that excludes more difficulties.

Most of the verification for correctness research area works under the following simplifications:

1.-No StackOverflow: we assume we have an infinite stack
2.-No MemoryOverflow: we assume we have an infinite heap
3.-I/O control: we assume no other process is editing our files
4.-Uncorrupted Root: we assume other processes can not randomly edit our memory bits
5.-Correctness of the OS: OS functionalities behave as expected
6.-Good Hardware: we assume no HW bugs
7.-Small Physics: no cosmic ray bit flips or funky quantum events
8.-Large Physics: no power cuts, no explosions or kicks to the HD
9.-Deployment: the code we checked is the one that will actually run
(Disclamer, my experience is mostly on OO verification)

Definitions

Thus, under those simplifications we can define Correctness as follows:
A program is correct if it always does the right thing
Where the specification identifies what is the acceptable range of right things.

Now we can contrast the definition of correctness with the one of
Security:
A program is secure if it never does the wrong thing

Warning: the scope is implicit.

At a first glance it may look like security is simply a subset of correctness. However, the SCOPE is often different.
When discussing about security we do not accept simplifications 1, 2 and 3; that is, even if there is a StackOverflow, we still can not accept to perform an invalid action.
In response to a StackOverflow it is ok to crash , but it is not ok to send our private information to another country.

Thus, usually we attempt to verify correctness under simplifications 1-2-3 and security without simplifications 1-2-3 (but still with simplifications 4-5-6-7-8-9).
In particular, without 1,2 near every program is simply incorrect.

While 'the right thing' is often defined using pre/post conditions in some logical framework, 'the wrong thing' is often defined using actions: we abstract over the internal state of the program and we just observe the interaction the program has with the rest of the world. Usually we can represent those interactions as forms of I/O or calls to low level OS functionalities.
Under this lens, terminating the program with an error message is often not considered an action. Going in loop is also often not considered an action.
(Models of security focusing on a unit of code often do not model Denial Of Service vulnerabilities; they are better addressed considering multiple processes running together, and thus out of scope for this discussion).

To further clarify the difference of security and correctness, consider the two examples below:

An universally secure(but not correct) solution to any problem

    throw new Error("NOPE!");

That is, we can simply refuse to act. No action means no security violation.

An universally correct (but not secure) solution to any problem

Assuming to have a function correctlyDoStuff(..) that is both correct and secure, we can forge a correct but not secure version of it:

    int doStuff(int x){
        try{rec(aNumber);}
        catch(StackOverflowError o){ badAction(); }
        return correctlyDoStuff(x);
    }
    void rec(int i){ if(i==0){return;} rec(i-1); }

where badAction does a security violation, like formatting the hard drive.
For any real execution environment of our code for our doStuff function, there exists a number aNumber that will trigger the StackOverflow, but in the verification for correctness model, the catch is recognized as dead code.
Indeed, some code verification tools will accept such a solution as correct.

Conclusions

There is a lot of confusion between correctness and security.
I hope I clarified the terms a little bit here.
Ultimately, there can not be full agreement on any terminology, but if we want something that can be mathematically modeled and checked/verified, the introduced terminology is a very good starting point.
Also, terminology in this area is so challenging that I do not think it is fair to require developers and companies to have a good grasp on those terms.
In particular, if you/your company want security and someones tries to sell you correctness without making sure that you understand the difference between the terms, they may be scamming you.

Overall, in my opinion we should start by writing SECURE software, and only after we are certain that we are well rooted in a secure environment we should start working toward CORRECTNESS.

How to avoid lambdas and still get most of the streams expressive power

Marco Servetto — Sun, 09 Jan 2022 21:13:10 +0000

Hi Everyone, I've just released a new video, talking about how with the slash we can avoid lambdas and still get most of the streams expressive power.
Also, it is probably the funniest video to date :-)

https://www.youtube.com/watch?v=3-EwmfpOAnA

42; multi-for-each and views

Marco Servetto — Sun, 02 Jan 2022 21:17:26 +0000

New 42 video OUT NOW
https://www.youtube.com/watch?v=jqux-j2wkVc
Did you ever wanted to iterate on multiple collections at the same time?
Did you never liked the functional 'zip' but you did not know why?
look to the video!

Advent of code, last puzzle

Marco Servetto — Sat, 25 Dec 2021 08:00:12 +0000

And this is the solution for the last day of advent of code 2021

reuse [L42.is/AdamsTowel]
Fs = Load:{reuse[L42.is/FileSystem]}

Cell = Collection.Enum:{
  Right={},Down={},Empty={}
  }
Map = (
  input = Fs.Real.#$of().read(\"input")
  var I col = 0I
  var I row = 0I
  for s in input.split(S.nl()) (row+=1I)
  for s in input.split(S.nl())().split() (col+=1I)
  Collection.matrix(Cell.List,row=row,col=col)
  )//row=137, col=139

Right = {class method Map.Coord (Map.Coord that) = 
  that.with(col=(\col+1I).mod(139I))
  }
Down = {class method Map.Coord (Map.Coord that)=
  that.with(row=(\row+1I).mod(137I))
  }

StepRight = {class method Map (Map map) =(
  res = Map(\()(for v in map \add(v)))
  for c in map.coords(), v in map if v==Cell.Right() (
    cr = Right(c)
    go = map.val(cr)==Cell.Empty()
    if go (
      res.set(cr val=v)
      res.set(c val=Cell.Empty())
      )
    )
  res
  )}
StepDown = {class method Map (Map map) =(
  res = Map(\()(for v in map \add(v)))
  for c in map.coords(), v in map if v==Cell.Down() (
    cd = Down(c)
    go = map.val(cd)==Cell.Empty()
    if go (
      res.set(cd val=v)
      res.set(c val=Cell.Empty())
      )
    )
  res
  )}

Main=(
  input = Fs.Real.#$of().read(\"input")
  var imm map = Map(\()(
    for s in input.split(S.nl()) for c in s.split()(
      if c==S"." ( \add(Cell.Empty()) )
      if c==S">" ( \add(Cell.Right()) )
      if c==S"v" ( \add(Cell.Down()) )
    )))
  res = 0I.acc()(while Bool.true() (
    new = StepDown(map=StepRight(map=map))
    if new==map ( Break() )
    map:=new
    v=\val
    \addOne
    ))
  Debug(res)

Overall, this adventure guided me to try many different kinds of algorithms in 42, and by doing so I discover a bunch of bugs and missing features in AdamsTowel.

Still, this programming style is very far from the ultimate goal of 42: Enforcing modular security.
This is where 42 shines, but this mostly emerges when the program is large enough that can not be reasonably done by a single programmer and where long term maintenance is kept into account.

I will be back to Dev.to after the new year break to talk more about the details of 42 and on how it enforces modular security.

Marco!

Advent of code Day 21

Marco Servetto — Tue, 21 Dec 2021 09:26:38 +0000

The two parts for the problem of today are well divided, so I will present them one at a time.
Or, if you prefer, you can just look to my comments on you tube:
(https://www.youtube.com/watch?v=61v1SNA79V0)

Part 1 is really trivial.
Note the trick with the modulo arithmetic, where we store a position that is 1 less than the intended position of the player.

D100 = Data:{
  var I rolled = 0I
  var I seed = 0I
  mut method I roll()=(
    \rolled(\rolled+1I)
    \seed((if \seed>=100I 0I else \seed)+1I)
    \seed
    )
  }
Player = Data:{
  var I pos
  var I points = 0I
  mut method Void turn(mut D100 that) =(
    tot = that.roll()+that.roll()+that.roll()
    \pos((\pos+tot).mod(10I)) //pos from 0--10, real pos is +1
    \points(\points+\pos+1I)
    )
  read method Bool won() = \points>=1000I
  }
Main=(
  p1 = Player(pos=0I) //1-1
  p2 = Player(pos=2I) //3-1
  dice = D100()
  while !p1.won() && !p2.won() (
    p1.turn(dice)
    if !p1.won() (p2.turn(dice))
    )
  if p1.won() (
    Debug(S"p2 loses for %p2.points(), %dice.rolled(), %(p2.points()*dice.rolled())")
    )
  if p2.won() (
    Debug(S"p1 loses for %p1.points(), %dice.rolled(), %(p1.points()*dice.rolled())")
    )
  //p1 loses for 671, 1338, 897798
  )

Part 2 is much more interesting, and it was feasible thanks to @Cache.Lazy; in this way our 'recursive' call may simply return a pre-computed value.

Report = Data:{
  Num p1Wins
  Num p2Wins
  method Bool open() = \p1Wins+\p2Wins==0Num
  method This +(This that) = This(
    p1Wins=this.p1Wins()+that.p1Wins(),
    p2Wins=this.p2Wins()+that.p2Wins()
    )
  }
State = Data:{
  I p1Pos
  I p2Pos
  I p1Score = 0I
  I p2Score = 0I
  method This turn(I p1Roll) = (
    (p1Pos0,p2Pos0,p1Score0,p2Score0) = this
    p1Pos = (p1Pos0+p1Roll).mod(10I) //from 0--10, real pos is +1
    p1Score = p1Score0+p1Pos+1I
    This(p1Pos=p1Pos,p2Pos=p2Pos0,
         p1Score=p1Score,p2Score=p2Score0)
    )
  method This turn(I p2Roll) = (
    (p1Pos0,p2Pos0,p1Score0,p2Score0) = this
    p2Pos = (p2Pos0+p2Roll).mod(10I) //from 0--10, real pos is +1
    p2Score = p2Score0+p2Pos+1I
    This(p1Pos=p1Pos0,p2Pos=p2Pos,
         p1Score=p1Score0,p2Score=p2Score)
    )
  method Report directWin() = {
    (p1Pos,p2Pos,p1Score,p2Score) = this
    X[p1Score<21I || p2Score<21I]
    if p1Score>=21I return \(p1Wins=1\ p2Wins=0\)
    if p2Score>=21I return \(p1Wins=0\ p2Wins=1\)
    return \(p1Wins=0\ p2Wins=0\)
    }
  @Cache.Lazy method Report wins() = {
    Debug(this)
    var res = this.directWin()
    if !res.open() return res
    r = Range(1I to=4I)      
    for a1 in r,for a2 in r,for a3 in r {
      stateA = this.turn(p1Roll=a1+a2+a3)
      resA = stateA.directWin()
      if !resA.open() return res+=resA
      return for b1 in r,for b2 in r,for b3 in r {
        stateB = stateA.turn(p2Roll=b1+b2+b3)
        resB = stateB.directWin()
        if !resB.open() return res+=resB
        return res+=stateB.wins()
        }
      }
    return res
    }
  }
Main = (
  s = State(p1Pos=0I,p2Pos=2I)
  Debug(s.wins())
  //Report(p1Wins=48868319769358,p2Wins=22432440913119)
  )
}

What do you think? with minor modifications I could combine automatic parallelism and automatic caching for an even faster version.

Advent of code Day 20

Marco Servetto — Mon, 20 Dec 2021 11:23:05 +0000

Finally a day where I can feel satisfied with my code results.
I explain this code in the detail on my youtube channel, (https://www.youtube.com/watch?v=lqA_XT0U4ng)

reuse [L42.is/AdamsTowel]

Fs = Load:{reuse[L42.is/FileSystem]}

Point = Data.AddList:Data:{ I x, I y
  method Point +(Point that) =
    \(x=this.x()+that.x(),y=this.y()+that.y())
  method Point max(Point that)=(
    (x0,y0) = this
    (x1,y1) = that
    Point(x=x0.max(x1),y=y0.max(y1))
    )
  method Point min(Point that) = 
    this.with(x=\x.min(that.x()))<:This.with(y=\y.min(that.y()))
  }

Map = Data:{
  M = Collection.map(key=Point,val=Bool)
  mut M map=\()
  var Bool outer=Bool.false()
  var Point topLeft = Point(x=0I,y=0I)
  var Point bottomRight = Point(x=0I,y=0I)

  mut method Void put(Point key, Bool val) = (
    \#map.put(key=key,val=val)
    \topLeft(\topLeft.min(key))
    \bottomRight(\bottomRight.max(key))
    )
  read method Bool val(Point key) =
    \map.val(key=key).val(orElse=this.outer())

  read method I nearBin(Point that) = 0I.acc()((
    var n = 512I
    for xi in Range(I"-1" to=2I), for yi in Range(I"-1" to=2I) (
      n/=2I
      if this.val(key=Point(x=xi,y=yi)+that) \add(n)
      )
    ))
  read method mut This step(Key that) = (
    mut This new = This()
    (x0,y0) = \topLeft
    (x1,y1) = \bottomRight
    for x in Range(x0-1I to=x1+2I), for y in Range(y0-1I to=y1+2I) (
      key=Point(x=x,y=y)
      i=\nearBin(key)
      X[i.isInRange(0I to=512I)] // is my binary conversion correct?
      new.put(key=key,val=that.val(i))
      )
    new.outer(if this.outer() that.right() else that.left())
    new
    )
  }
Key = Collection.list(Bool)

Main=(
  input = Fs.Real.#$of().read(\"input").split(S.nl()++S.nl())
  imm key = Key()( for i in input().split() \add(i==S"#") )
  X[key.size()==512I]
  var map = Map()
  for line in input().split(S.nl()), li in Range.unbounded() (
    for c in line.split(), ci in Range.unbounded() (
      map.put(key=\(x=li,y=ci),val=c==S"#")
      )
    )
  for i in Range(2I) ( map:=map.step(key) )  //50I
  tot = 0I.acc()(for (val) in map.map() \addIf(val))
  Debug(tot)
  )

Advent of code Day 18

Marco Servetto — Sat, 18 Dec 2021 21:41:28 +0000

(Note: for more 42, go to: https://www.youtube.com/MarcoServetto)
Ok, finally I have a solution for day 18.
Those tasks are getting more complex day after day.
This time part 2 was trivial after doing part1.

reuse [L42.is/AdamsTowel]

Fs = Load:{reuse[L42.is/FileSystem]}

Unit = Load:{reuse[L42.is/Unit]}

Tree = {interface [HasToS]
  method I magnitude()
  method Tree reduce()
  }  
Trees = Collection.list(Tree)

Leaf = Class:Trait(Unit(I)):{[Tree]
  method magnitude()=\#inner

  method reduce()={
    if \#inner<10I return this
    half1 = \#inner/2I
    half2 = if half1+half1==\#inner half1 else half1+1I
    return Node(left=This(half1),right=This(half2))
    }
  }  
Node = Data:{[Tree,HasToS]
  Tree left, Tree right

  method toS()=S"[%this.left(),%this.right()]"

  method I magnitude() = 
    (\left.magnitude()*3I)+(\right.magnitude()*2I)

  method reduce()={
    Explode(Tree tree) = Explode(k=0I,t=this)
    if tree.toS()!=this.toS() return tree.reduce()
    Tree split = Split(this)
    if split.toS()!=this.toS() return split.reduce()
    return this
    }
  }
Split = {class method Tree(Tree that)={
  if Node(left,right)=that (
    l = This(left)
    if l.toS()!=left.toS() return Node(left=l,right=right)
    return Node(left=l,right=This(right))
    )
  return that.reduce()
  }}
Explode = Data:{
  I left,Tree tree, I right 
  class method This(I k, Tree t) = {
    if t<:Leaf return This(left=0I,tree=t,right=0I)
    if t<:Node (
      return \node(k=k,t=t)
      )
    error X"exaustive Leaf+Node"
    }
  class method This node4(Node t) = {
    if (Leaf left,Leaf right) = t return This(left=left.#inner(),tree=Leaf"0",right=right.#inner())
    error X"exaustive %t"
    }
  class method This node(I k,Node t) = {
    (left,right)=t
    sLeft  = \stable(k=k+1I,t=left)
    sRight = \stable(k=k+1I,t=right) 
    if sLeft && sRight return This(left=0I,tree=t,right=0I)
    (left1,tree,right2)=This(k=k+1I t=if !sLeft left else right)
    if !sLeft return This(left=left1
    ,,tree=Node(left=tree,right=This.sumLeft(n=right2,t=right)) right=0I)
    return This(left=0I
    ,,tree=Node(left=This.sumRight(n=left1,t=left),right=tree) right=right2)
    }
  class method Bool stable(I k, Tree t) = {
    if Node(left,right)=t return k!=4I && \stable(k=k+1I,t=left) && \stable(k=k+1I, t=right)
    return Bool.true()
    }
   class method Tree sumLeft(I n,Tree t) = {
     if t<:Leaf return t+Leaf(n)
     if Node(left,right)=t return Node(left=this.sumLeft(n=n,t=left),right=right)
     error X"exaustive"
     }
   class method Tree sumRight(I n,Tree t) = {
     if t<:Leaf return t+Leaf(n)
     if Node(left,right)=t return Node(left=left, right=this.sumRight(n=n,t=right))
     error X"exaustive"
     }
  }
ParseTree = Data:{
  S string
  var I index = 0I
  mut method Bool check(S that) = 
    \string.startsWith(that leftOffSet=this.index())
  mut method Void pop(S that) = (
     X[this.check(that)]
     \index(\index+that.size())
     )
  mut method S take(S until) = (
    (string,index) = this
    i = string.indexOf(until from=index)
    \index(i)
    string.subString(index to=i)
    )
  mut method Tree(S t) = 
    if !\check(S"[") \leaf(t=t) else \node(t=t)

  mut method Leaf leaf(S t) = \(string=this.take(until=t))

  mut method Node node(S t) = (
    \pop(S"[")
    left = this(t=S",")
    \pop(S",")
    right = this(t=S"]")
    \pop(S"]")
    Node(left=left,right=right)
    )
  }
SumAll = {class method Tree (Trees that) = {
  X[!that.isEmpty()]
  (size,left,withoutLeft) = that
  if size==1I return left
  res  = Node(left=left,right=withoutLeft.left()).reduce()
  return This(withoutLeft.with(left=res))
  }}
SumMax = {
  class method I (Trees that) = (
    exp=This.expand(that)
    0I.acc()(for e in exp, i in Range(exp.size()) (
      \val(\val.max(e.reduce().magnitude()))
      ))
    )
  class method Trees expand(Trees that) = \()(
    for a in that for b in that if a.toS()!=b.toS() (
      \add(Node(left=a,right=b))
      ))
  }
Main=(
  input = Fs.Real.#$of().read(\"input")
  imm trees = Trees()(for line in input.split(S.nl()) \add(ParseTree(string=line)(t=S"")))
  all=SumAll(trees)
  Debug(all.magnitude())//3647
  max=SumMax(trees)
  Debug(max)//4600
  )

Now, figuring out the explosion algorithm was quite challenging, and I had to switch using the 'formal language' that is commonly used for designing programming languages.
If you are curious, here is explode in formalism:

 #define explode(k,t) = n1 t n2 //0 if none
 explode(k,n) = empty,n,empty
 explode(4,[n1,n2]) = n1,0,n2
 explode(k,[t1,t2]) = [t1,t2]
   k!=4
   stable(k,t1)
   stable(k,t2)
 explode(k,[t1,t2]) = n1,[t1',sumLeft(n2,t2)],0
   k!=4
   !stable(k,t1)
   n1,t1',n2 = explode(k+1,t1)
 explode(k,[t1,t2]) = 0,[sumRight(n1,t1),t2'],n2
   k!=4
   stable(k,t1)
   !stable(k,t2)
   n1,t2',n2 = explode(k+1,t2)   

 stable(k,n)
 stable(k,[t1,t2]) = k!=4 && stable(k+1,t1) && stable(k+1,t2)

 sumLeft(n0,n) = n+n0
 sumLeft(n0,[t1,t2]) = [sumLeft(n0,t1),t2]
 sumRight(n0,n) = n+n0
 sumRight(n0,[t1,t2]) = [t1,sumRight(n0,t2)]

As you can see, I'm using a functional approach to do the reduction.
I'm not sure if a 'mutation' based approach would have been easier.

Advent of code Day 17

Marco Servetto — Fri, 17 Dec 2021 21:16:23 +0000

Nothing special to discuss this time.
I think I've done the dumbest exhaustive search ever, without even too much consideration to get good bounds.
The interesting bit is the formatting:
do you think this code is formatted ok? in 42 you can write in a very different style, and it is not clear how to format certain things.

reuse [L42.is/AdamsTowel]
Point = Data:{Num x, Num y}
Velocity = Data:{Num x, Num y}
Probe = Data:{
  var Point location = \(x=0Num,y=0Num)
  var Velocity velocity
  mut method Void step() = (
    (x,y) = \velocity
    \location(\location.with(x=\x+x).with(y=\y+y))
    \velocity(\velocity
      .with(x=0Num.max(x-1Num)).with(y=y-1Num))
    )
  }
Square = Data:{
  Num x1, Num x2, Num y1, Num y2
  method Bool #in1 (Point that)=
    that.x().isInRange(this.x1() to=this.x2()) 
    && that.y().isInRange(this.y1() to=this.y2())
  }

Main = (
  //input=S"target area: x=88..125, y=-157..-103"
  Square target=Square(
    x1=88Num x2=126Num y1=Num"-157" y2=Num"-102")
  result = 0Num.acc()(
    for x in Range(0I to=1000I),
    for y in Range(I"-300" to=1500I) (
      v = Velocity(x=\(x),y=\(y))
      p = Probe(velocity=v)
      res = 0Num.acc()(while !(p.location() in target) 
        ,,&& p.location().y()>=target.y1()
        ,,&& p.location().x()<=target.x2() ( 
        p.step() 
        \val(\val.max(p.location().y()))
        ))
      //Part1
      //if p.location() in target \val(\val.max(res))
      if p.location() in target \addOne()//Part2
      //\val(\val.max(res))
      )
    )
  Debug(result)//12246 and 3528
  )

For example, consider this part:

res = 0Num.acc()(while !(p.location() in target) 
  ,,&& p.location().y()>=target.y1()
  ,,&& p.location().x()<=target.x2() ( 
  p.step() 
  \val(\val.max(p.location().y()))
  ))

In 42 the comma (,) is just a spacing character like space and new line, so we can use it as often as we want. In practice, it can be used to distinguish different kinds of indentation.
Here I'm using it to differentiate the indentation of the long while condition and the indentation of the while body.
This is further complicated by the fact that the while is the argument of the #apply method of Num.Acc.

Ideas?