Thanks for the feedback topic. I've been working on this code for some time, based on the proposals as they came (with the Swift nightly snapshots), and I was hoping I'd be able to actually get to a compiled binary using Xcode 13 beta and Swift 5.5; unfortunately, at this point the compilation never completes, no matter how long I wait (needless to say, I did fix any error or warning that previously came up).
//
// Created by Pierre Lebeaupin on 17/01/2021.
// Copyright © 2021 Pierre Lebeaupin. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
import Foundation;
enum Op: String {
case additive = "+", multiplicative = "*";
func neutralValue() -> UInt32 {
return ((self == .additive) ? 0 : 1);
}
func combine(_ a: UInt32, _ b: UInt32) -> UInt32 {
return ((self == .additive) ? (a + b) : (a * b));
}
func uncombine(_ a: UInt32, _ b: UInt32) -> UInt32 {
return ((self == .additive) ? (a - b) : (a / b));
}
}
struct ReadyValue {
let value: UInt32;
let op: Op?;
let description: () -> String;
// Note that as a closure, it can depend on more than the stored properties, contrary to a
// computed property.
init(_ inValue: UInt32) {
value = inValue;
op = nil;
description = { return inValue.description;};
}
init(value inValue: UInt32, op inOp: Op, description indescription: @escaping () -> String) {
value = inValue;
op = inOp;
description = indescription;
}
}
struct DispatchedFunctor {
typealias Dispatcher = (_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void?,
_ dispatched: DispatchedFunctor) async -> Void;
let apply: (_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void?,
_ dispatcher: Dispatcher) async -> Void;
}
func resolveCore(_ injectedDispatcher: DispatchedFunctor.Dispatcher, _ resultReceiver: @escaping (_ result: String) -> Void, _ startGoal: UInt32, _ primitives: [UInt32]) async {
// await { () async -> Void in
var referenceL = [ReadyValue]();
var referenceComposedCount = 0;
var referenceOtherComposedCount = 0;
for element in primitives {
referenceL.append(ReadyValue(element));
}
await exploreAdditionOfRightNode(&referenceL,
&referenceComposedCount,
&referenceOtherComposedCount,
injectedDispatcher,
kind: .additive);
await exploreAdditionOfRightNode(&referenceL,
&referenceComposedCount,
&referenceOtherComposedCount,
injectedDispatcher,
kind: .multiplicative);
// }(); // https://bugs.swift.org/browse/SR-12243
@Sendable func exploreAdditionOfRightNode(_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ dispatcher: DispatchedFunctor.Dispatcher,
kind: Op) async {
if (l.count != 0) && (l[l.count - 1].op != kind) {
guard otherComposedCount == 0 else {
return;
}
otherComposedCount = composedCount;
composedCount = 0;
}
defer {
if (l.count != 0) && (l[l.count - 1].op != kind) {
composedCount = otherComposedCount;
otherComposedCount = 0;
}
}
var referenceDecomposedValue = [false: kind.neutralValue(), true: kind.neutralValue()];
await dispatcher(&l,
&composedCount,
&otherComposedCount,
&referenceDecomposedValue,
kind,
/* startingFrom: */ 0,
{ _ in return nil;},
DispatchedFunctor(apply: iteratePossibleLeftNodes));
}
@Sendable func iteratePossibleLeftNodes(_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void?,
_ dispatcher: DispatchedFunctor.Dispatcher) async {
for candidateOffset in startingFrom ..< (l.count - composedCount) {
let rightChild = l.remove(at: candidateOffset);
if let _ = rightChild.op {
otherComposedCount -= 1;
}
defer {
if let _ = rightChild.op {
otherComposedCount += 1;
}
l.insert(rightChild, at: candidateOffset);
}
for phase in 0...1 {
let reverse = (phase == 1);
{ (_ valueComponent: inout UInt32) in
valueComponent = kind.combine(valueComponent, rightChild.value);
}(&decomposedValue[reverse]!);
defer {
{ (_ valueComponent: inout UInt32) in
valueComponent = kind.uncombine(valueComponent, rightChild.value);
}(&decomposedValue[reverse]!);
}
let selfNode = {(_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void? in
return action(rightChild, reverse) ?? walkOperands(action);
};
await dispatcher(&l,
&composedCount,
&otherComposedCount,
&decomposedValue,
kind,
/* startingFrom: */ candidateOffset,
selfNode,
DispatchedFunctor(apply: iteratePossibleLeftNodes));
// close current composition
var num = 0;
guard (selfNode({_,_ in guard num == 0 else {return ();}; num += 1; return nil;}) != nil)
&& ( (kind == .additive) ? decomposedValue[false]! > decomposedValue[true]! :
((decomposedValue[false]! % decomposedValue[true]!) == 0) ) else {
continue;
}
let realizedValue = kind.uncombine(decomposedValue[false]!, decomposedValue[true]!);
let description = { () -> String in
var current = "(";
selfNode({(_ value: ReadyValue, _ freverse: Bool) -> Void? in
current += " ";
current += (freverse ? (kind == .additive ? "-" : "/") : kind.rawValue);
current += " ";
current += value.description();
return nil;
});
current += ")";
return current;
};
guard l.count > 0 else {
if realizedValue == startGoal {
resultReceiver(description());
}
continue;
}
composedCount += 1;
l.append(ReadyValue(value: realizedValue, op: kind, description: description));
defer {
l.remove(at: l.count - 1);
composedCount -= 1;
}
await exploreAdditionOfRightNode(&l,
&composedCount,
&otherComposedCount,
dispatcher,
kind: .additive);
await exploreAdditionOfRightNode(&l,
&composedCount,
&otherComposedCount,
dispatcher,
kind: .multiplicative);
}
}
}
}
@Sendable func iteratePossibleLeftNodesFakeDispatch(_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void?,
_ inner: DispatchedFunctor) async {
await inner.apply(&l,
&composedCount,
&otherComposedCount,
&decomposedValue,
kind,
startingFrom,
walkOperands,
iteratePossibleLeftNodesFakeDispatch);
}
@available(macOS 12.0, *) protocol ResultReceiver: Actor {
func receive(result: String);
}
@available(macOS 12.0, *) func resolveAsync(_ resultReceiver: ResultReceiver, _ startGoal: UInt32, _ primitives: UInt32...) async {
await withTaskGroup(of: Void.self) {group in
var outstandingTasks = UInt(0);
func iteratePossibleLeftNodesDispatch(_ l: inout [ReadyValue],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping (_ action: (_ value: ReadyValue, _ reverse: Bool) -> Void?) -> Void?,
_ inner: DispatchedFunctor) async {
let workloadEstimator = l.count + (walkOperands({_,_ in return ();}) != nil ? 1 : 0);
/* Among other properties, this estimator value is monotonic. */
// 6 may be too many to fit in a tick (1/60th of a second)
// 4 already means too few possibilities to explore
// 3 is right out
if workloadEstimator == 5 {
// reseat this divergence over a copy of the whole state
let paramL = l;
let paramComposedCount = composedCount;
let paramOtherComposedCount = otherComposedCount;
let paramDecomposedValue = decomposedValue;
group.spawn {
var childL = paramL;
var childComposedCount = paramComposedCount;
var childOtherComposedCount = paramOtherComposedCount;
var childDecomposedValue = paramDecomposedValue;
await inner.apply(&childL,
&childComposedCount,
&childOtherComposedCount,
&childDecomposedValue,
kind,
startingFrom,
walkOperands,
iteratePossibleLeftNodesFakeDispatch);
}
outstandingTasks += 1;
while outstandingTasks >= ProcessInfo.processInfo.activeProcessorCount {
_ = await group.next();
outstandingTasks -= 1;
}
/* Note that as a result, the code will adapt in case activeProcessorCount changes.
At least, it will do so eventually, not with any sort of timeliness: for example,
if activeProcessorCount increases somehow, we will have to wait for one task to
complete before the code will work towards making outstandingTasks equal the new
value. */
} else {
await inner.apply(&l,
&composedCount,
&otherComposedCount,
&decomposedValue,
kind,
startingFrom,
walkOperands,
iteratePossibleLeftNodesDispatch);
}
}
await resolveCore(iteratePossibleLeftNodesDispatch, {result in
async {
await resultReceiver.receive(result: result);
}
}, startGoal, primitives);
// outstanding tasks in the group are awaited at that point, according to the spec
// https://github.com/DougGregor/swift-evolution/blob/structured-concurrency/proposals/nnnn-structured-concurrency.md
};
}
(you ought to be able to try it out with, say, await resolveAsync(printerActor, 70, 5, 4, 3, 2, 2);
)
This is derived from code that does work, using GCD instead: http://wanderingcoder.net/2021/01/13/second-teaser-practical-multithreading/ ; I can't locate any diagnostic info for this failure, is there anything you would like me to try to provide you some?